pushback

 재귀가 익숙하지 않으면 풀기 힘든 문제다. 근데 알고보면 별 거 없다.

 \(n = 3\)의 별 모양을 보자

 \(n = 9\)인 것을 보자

가운데 \(n = 3\)의 별 모양 하나가 빠진 모양이다.

\(n = 27\)인 것을 보자.

 가운데 \(n = 9\)의 별 모양 하나가 빠진 모양이다.

 끝났다. \(n = 3^k\)의 별 모양은 \(n = 3^{k - 1}\) 별 모양 하나가 가운데에 비어있는 모양이다.

 \(n = 3^k\)부터 \(n = 1\)까지 재귀적으로 별 모양을 그리면 원하는 별 모양을 얻을 수 있다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

char star[2201][2201] = { 0 , };

void recur(int x, int y, int cur)
{
	// n = 1이면 별 찍고 리턴
    if (cur == 1)
    {
        star[x][y] = '*';
        return;
    }
    
    int next = cur / 3;
	
    // 가운데 빼고 재귀로 돌기
    // 1 2 3
    // 4   6
    // 7 8 9
    // 항상 이렇게 이중 for문이 돈다.
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (i == 1 && j == 1) // 가운데는 스킵
                continue;
            else
                recur(x + (i * next), y + (j * next), next);
        }
    }		
}
int main()
{
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    // 모두 빈칸으로 초기화
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) star[i][j] = ' ';

    // 재귀 시작
    recur(0, 0, n);
	
    // 출력
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << star[i][j];
        }
        cout << '\n';
    }
	
    return 0;
}

팩토리얼 문제와 달리 이번 문제는 친절하게 점화식이 나왔다. 이를 이용해서 재귀로 작성해보자.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int fibo(int n) {
    if (n <= 1) return n;
    else return fibo(n - 1) + fibo(n - 2);
}

int main()
{
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
	
    cout << fibo(n);
	
    return 0;
}

 팩토리얼 문제는 나중에 나올 Dynamic Programming(= DP)로 푸는 것이 훨씬 효율적이지만, 문제가 속해있는 단계 자체가 재귀이고 \(n\)의 범위도 12까지이니 간단하게 재귀로 해결하자.

 재귀로 구현해야 할 것은 하나이다.

 어떤 자연수\(n\)이 있을 때, \(n! = n * (n - 1)!\)임은 자명하다.

 이것을 이용해서 재귀함수를 한번 작성해보면

이런 코드를 작성할 수 있다.

 물론 단순히 for문을 사용하여 팩토리얼을 구할 수도 있지만, 팩토리얼 같이 점화식이 존재한다면 재귀로 구할 수 있다는 점만 알고 넘어가자.

 점화식이 있는 문제에 대해선 나중에 나올 DP 파트에서 자세히 다뤄보겠다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int fact(int n) {
    if (n <= 1) return 1;
    else return n * fact(n - 1);
}

int main()
{
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
	
    cout << fact(n);
	
    return 0;
}

 문제에 뭔가 열심히 적혀있는데 결국엔 두 원이 만나는 점의 개수를 구하면 된다.

 두 원의 중심이 같으면 반지름에 따라 모든 점에서 만나거나 만나는 점이 없다.

 중심이 다르면 만나지 않거나, 한 점에서 접하거나, 두 점에서 만나게 된다.

 이 개념만 알고 코딩하면 되는데 그게 마음처럼 쉽게 안된다. 그래서 아마 이 글을 보고 있을 것이다.

 하나씩 짚어보자.

 두 원의 중심이 같으면 반지름이 같은지 확인하여 반지름이 같으면 -1 출력, 다르면 0을 출력해주면 된다.

 문제는 중심이 다를 때이다. 

 중심이 다를 때 만나지 않는 경우는 두 가지이다.

 두 원이 아주 떨어져 있거나, 한 원 안에 다른 원이 들어가 있는 경우인데 나같은 경우 아주 떨어진 경우만 생각했다가 두번의 WA를 받았다. 

 이 두 상황을 판단하는 방법은

• 두 원이 아주 떨어져 있는 경우 : 두 원의 반지름의 합 < 두 중심 사이의 거리
• 한 원 안에 다른 원이 있는 경우 : 두 원의 반지름의 차 > 두 중심 사이의 거리  

 이다.

마찬가지로 두 원이 한 점에서 만나는 경우는

그림과 같이 두 가지 경우가 나온다. 

• 두 원이 떨어져 있는 경우 : 두 원의 반지름의 합 == 두 중심 사이의 거리
• 한 원 안에 다른 원이 있는 경우 : 두 원의 반지름의 차 == 두 중심 사이의 거리  

마지막으로 두 원이 두 점에서 만나는 경우는

 위와 같이 두 가지 경우인 것 같아 보여서 아래와 같이 

• 두 원이 떨어져 있는 경우 : 두 원의 반지름의 합 > 두 중심 사이의 거리
• 한 원 안에 다른 원이 있는 경우 : 두 원의 반지름의 차 < 두 중심 사이의 거리 

 나누어 생각하면 망한다. 사실 위에 두 경우는 같은 경우이므로, 두 점에서 만날 때는 위에 두 조건을 동시에 만족해야한다.  

 결론적으로 중심이 다를 때 두 원의 중심 사이의 거리를 \(d\), 두 원의 반지름을 \(r_1\), \(r_2\)라고 하면,

• 교점 X : \( r_1 + r_2 < d\)    or    \( |r_1 - r_2| > d\)
• 교점 1 : \(r_1 + r_2 = d\)    or    \(r_1 - r_2 = d\)
• 교점 2 : \(|r_1 - r_2|    <    d    <    r_1 + r_2\)

 이렇게 정리할 수 있고, 코딩만 하면 끝난다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    int first_x, first_y, first_r, second_x, second_y, second_r;
    int d, r;
    
    while (T--) {
        cin >> first_x >> first_y >> first_r >> second_x >> second_y >> second_r;
        // d : (두 점 사이의 거리) ^ 2
        d = (first_x - second_x) * (first_x - second_x) + (first_y - second_y) * (first_y - second_y);

        // 중심이 같은 경우
        if (d == 0) {
            if (first_r == second_r) {
                cout << -1 << '\n';
            }
            else{
                cout << 0 << '\n';
            }
        }
        // 중심이 다를 때
        else {
            // 미리 구해놓은 d가 거리의 제곱이므로 양변을 제곱해준다.
            // r1 + r2 < d || |r1 - r2| > d
            if ((first_r + second_r) * (first_r + second_r) < d || d < (first_r - second_r) * (first_r - second_r) ) {
                cout << 0 << '\n';
            }
            // r1 + r2 == d || |r1 - r2| == d
            else if ((first_r + second_r) * (first_r + second_r) == d || (first_r - second_r) * (first_r - second_r) == d) {
                cout << 1 << '\n';
            }
            // |r1 - r2| < d < r1 + r2
            else if ((first_r - second_r) * (first_r - second_r) < d && d < (first_r + second_r) * (first_r + second_r) ){
                cout << 2 << '\n';
            }
        }
    }

    return 0;
}

 유클리드 기하학에서 원의 넓이는 우리가 아는 원의 넓이이고,

 택시 기하학에서 원의 넓이는 대각선의 길이가 \(2n\)인 정사각형의 넓이와 같다.

 실수 출력에서만 조금 신경 써주면 충분히 해결할 수 있는 문제이다.

 아래 코드에 printf를 이용한 실수 출력과 cout을 이용한 실수 출력 두 가지 모두 적어놓았으니, 이 부분은 외우자.

#include <bits/stdc++.h>

#define pi 3.14159265359
using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MAX_N = 1e5 + 1;
const int MOD = 1e+9;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	
    double n;
    cin >> n;

    // printf
    // 소수점 아래 x자리만큼 출력하고 싶으면 %0.xf로 사용
    printf("%0.7f\n%0.7f", n * n * pi, n * n * 2);
    
    // cout
    cout << fixed; // 소수점 자리수를 고정함
    cout.precision(7); // 몇 자리를 출력할지 정함
    cout << n * n * pi << '\n' << n * n * 2; // fixed

    return 0;
}

 간단하게 우리가 알고 있는 피타고라스를 쓰면 된다. 대신 컴퓨터는 항상 정확한 루트 값을 갖고 온다는 가정을 할 수 없기 때문에, 

\(가장 긴 변 = \sqrt{한 변^2 + 다른 한 변^2}\) 이 아닌

\(가장 긴 변^2 = 한 변^2 + 다른 한 변^2\) 을 만족하는지 확인한다.

 당연하게도 가장 긴 변은 빗변이겠지만, 문제에서 빗변이 어떤 것인지 입력으로 알려주지 않기 때문에 입력을 받아 가장 긴 변을 빗변으로 설정해주어야 한다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    vector<int> v(3);
    while (true) {
        cin >> v[0] >> v[1] >> v[2];
        if (v[0] == 0 && v[1] == 0 && v[2] == 0)
            break;
        sort(v.begin(), v.end());

        if (v[2] * v[2] == v[0] * v[0] + v[1] * v[1]){
            cout << "right\n";
        }
        else{
            cout << "wrong\n";
        }
    }
    return 0;
}

 세 점을 갖고 상대적으로 위치를 찾아내는 방법도 있겠지만, 생각보다 귀찮(?)아서 1001개짜리 배열 \(x\)와 \(y\)을 이용해서 풀었다.

 풀이는 이렇다.

 1. 입력 받은 세 점의 좌표에 해당하는 원소들을 먼저 1씩 증가시켜준다.

 2. \(x\)와 \(y\)배열을 1~1000까지 돌면서 원소가 1인 곳을 체크해서 답으로 저장해준다.

 3. 찾은 좌표를 출력한다.

 직사각형이기 때문에 네 점의 좌표는 항상 (a, c) , (a, d), (b, c), (b, d)의 형태를 유지한다는 점을 이용하였다. ( 항상 a, b, c, d가 2개씩 등장)

#include <bits/stdc++.h>
using namespace std;

int x[1001] = { 0 , };
int y[1001] = { 0 , };

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    
	for (int i = 0; i < 3; i++) {
		int a, b;
		cin >> a >> b;
		x[a]++;
		y[b]++;
	}
	
	int ans_x = -1, ans_y = -1;
    
	for (int i = 0; i < 1001; i++) {
		if (x[i] == 1) ans_x = i;
		if (y[i] == 1) ans_y = i;
		if (ans_x != -1 && ans_y != -1)
			break;
	}
	
	cout << ans_x << ' ' << ans_y;

	return 0;
}

\((x, y)\)가 직사각형 안에 존재하는 점이기 때문에 직사각형의 네 경계선까지 거리는 무리없이 구할 수 있다.

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int x, y, w, h;
	cin >> x >> y >> w >> h;
	int ans = min({x, w - x, y, h - y});
	cout << ans;
	return 0;
}