[BaekJoon 1057번] 토너먼트(C++)

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

[문제 풀이 사이트]

1057번: 토너먼트

[문제 설명]

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.
마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.

[입력]

첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다. N은 2보다 크거나 같고, 100,000보다 작거나 같은 자연수이고, 김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.

[출력]

첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 만약 서로 대결하지 않을 때는 -1을 출력한다.

[입출력 예]

입력	출력
16 1 2	1
16 8 9	4
1000 20 31	4
65536 1000 35000	16
60000 101 891	10

[문제 풀이]

프로그래머스의 예상 대진표와 같은 문제이다.
이번엔 규칙을 찾아서 코드를 작성했다.

예를 들어 참가자 수가 6명, 지민이의 번호가 1, 임한수의 번호가 5로 주어진다면
아래와 같은 대진표를 작성할 수 있다.

지민이와 한수는 3 라운드에서 만나게 된다.
지민이는 1 ➜ 1 ➜ 1 ➜ 대결
한수는 5 ➜ 3 ➜ 2 ➜ 대결

지민이와 한수가 대결하는 경우는 지민이의 번호와 한수의 번호가 같아질 때이고,
참가자의 번호가 짝수 또는 홀수의 경우 참가자의 번호 = (참가자의 번호 / 2) + (참가자의 번호 % 2)라는 규칙을 찾을 수 있다.

그리고 문제에서 서로 대결하지 않을 때는 -1을 출력하는데,
아무리 테스트케이스를 생각해봐도 서로 대결하지 않는 경우의 수가 없어서 따로 코드로 작성하지는 않았다

[최종 코드]

[GitHub]

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

#include <bits/stdc++.h>

using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int ans = 0;
    int N;
    int jimin, hansu;
    cin >> N >> jimin >> hansu;
    while(jimin != hansu) {
        jimin = jimin / 2 + jimin % 2;
        hansu = hansu / 2 + hansu % 2;
        if(jimin==hansu) {
            ans += 1;
            break;
        }
        ans += 1;
    }
    cout << ans;
    return 0;
}