백준 1057 - 토너먼트

C++

1057 번 - 토너먼트

문제

1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.

문제 출처

접근 방법

일단 먼저 그림을 그려 보았다.

그림을 그리고 보니 보이는 규칙이 있었다.

1. 2개의 수 중 작은 수가 짝수 일 때 큰 수와 매칭 될 수 없다. 따라서 (8, 9)끼리 매칭 될 수 없으며, 작은 수가 홀 수 일때 큰 수와 1차이가 나면 서로 대결을 한다는 것이다. ex (1,2), (7,8) 등등
2. 라운드가 증가 할 때마다, 각 수는 (n + 1) / 2으로 재배정 받는다.

위의 2개의 규칙을 이용하면, 작은 수가 홀 수 일때 큰 수와 1 차이나는지 확인하고 아니면 재배정 하는 방식으로 while문을 반복하면 언젠간 만나게 되고, 그때의 round를 출력하고 빠져나온다.

구현

먼저 입력이 큰 수가 먼저 들어올 경우를 대비하기 위해, 작은 수는 a 큰 수는 b에 입력되게 해준다. 이후 while문을 반복하여 두 수가 매칭되는 경우를 찾는다.

코드

#include <iostream>

using namespace std;

int n, a, b, rnd = 1;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> a >> b;
    if (a > b) {
        int temp = b;
        b = a;
        a = temp;
    }
    while (1) {
        if (a % 2 == 1) {			//작은 수가 홀 수 일때
            if (a == b - 1) {		//큰 수와 1이 차이난다 == 두 수가 매칭 됨
                cout << rnd;
                break;
            }
        }
        a = (a + 1) / 2;			//번호 재 배정
        b = (b + 1) / 2;
        rnd++;
    }
    
    return 0;
}

후기 및 개선할 점

1시간 정도 처음 세운 식에서 예외를 찾는데 시간을 많이 투자하였다. 하지만 의외로 저 식으로 다 해결되더라