[BOJ_C++] 2078번 : 무한이진트리

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int a, b; cin >> a >> b;
    int x, y; x = y = 0;

    while (true) {
        if (a == 1) {
            y += b - 1; break;
        }
        else if (b == 1) {
            x += a - 1; break;
        }

        if (a > b) x += a / b, a %= b;
        else y += b / a, b %= a;
    }

    printf("%d %d", x, y);

    return 0;
}

• 무조건 이동한 방향의 값이 커진다.
• 만약, a 또는 b가 1이라면 한 쪽으로만 이동한 경우로 이동 횟수는 1이 아닌 값에서 1을 뺀만큼 이동한 것이다. 따라서 a가 1이면 y는 b-1이고, b가 1이면 x는 a-1이 된다.
• 이외의 이동은 a와 b 중 큰 값을 가지는 방향으로 이동한 것이므로 해당 방향의 카운트를 a / b 또는 b / a 크기만큼 더한다.
• 이때 나눈 몫을 저장하는 이유는 이동을 할 때 값을 서로 더하기 때문에 이동한 방향의 수는 반대의 값으로 나눈 값이 바로 이동한 횟수가 되기 때문이다.
• 각 방향으로 이동한 횟수를 출력하고 프로그램을 종료한다.

결과