백준 1057: 토너먼트 C++

백준 1057: 토너먼트 C++

문제

N명이 참가하는 토너먼트가 있습니다.
1번부터 N번까지 번호를 받고, 인접한 사람끼리 게임을 합니다.
이긴 사람은 다음 라운드로 진출하며, 번호는 기존 순서를 유지한 채 새롭게 1번부터 재배정됩니다.
만약 홀수 명이라면 마지막 사람은 자동으로 진출합니다.
김지민과 임한수는 서로 대결하기 전까지는 항상 이긴다고 가정합니다.
이 두 사람이 몇 라운드에서 처음 대결하는지 출력하는 프로그램을 작성합니다.
만약 끝까지 대결하지 못하면 -1을 출력합니다.

아이디어

문제를 해결하기 위해 핵심 아이디어를 단계별로 정리하였습니다.
각 단계는 간단하면서도 직관적입니다.

1️⃣ 값은 2분의 1씩 줄어든다

매 라운드마다 참가자 수가 절반으로 줄어들며, 번호도 (번호+1)/2로 갱신됩니다.
두 사람도 계속 이기면서 올라가기 때문에 서로의 번호도 계속 절반으로 줄어들어 가까워집니다.

예를 들어 참가자 수 8명인 경우 토너먼트 진행은 아래처럼 됩니다.

Round 1:   1   2   3   4   5   6   7   8
          |___|   |___|   |___|   |___|
Round 2:     1       2       3       4
            |_______|       |_______|
Round 3:         1               2
                      |_______________|
Round 4:                1

• Round 1: 8명이 각각 붙어 4명으로 줄어듭니다.
• Round 2: 4명이 각각 붙어 2명으로 줄어듭니다.
• Round 3: 2명이 붙어 1명이 됩니다.
• 각 단계마다 참가자 수가 절반으로 줄어듭니다.

2️⃣ 두 값의 차이가 1이 될 때를 찾는다

두 사람이 맞붙는 상황은 번호가 인접하고, 작은 쪽이 홀수, 큰 쪽이 짝수인 경우입니다.
즉, abs(n1 - n2) == 1이면서 min(n1, n2)가 홀수이고 max(n1, n2)가 짝수일 때만 대결합니다.

예시 1: 3과 4

Round:   1   2   3   4   5   6   7   8
          |___|   |___|   |___|   |___|

다음 라운드 번호:   1   2   3   4

• 3과 4는 같은 그룹(|___|)으로 묶여서 맞붙습니다.
• 작은 번호 3이 홀수, 큰 번호 4가 짝수이므로 대결합니다.

예시 2: 4와 5

Round:   1   2   3   4   5   6   7   8
          |___|   |___|   |___|   |___|

다음 라운드 번호:   1   2   3   4

• 4는 2번 그룹, 5는 3번 그룹으로 배정됩니다.
• 서로 다른 그룹에 속해 있기 때문에 이 라운드에서는 대결하지 않습니다.

번호 쌍	대결 여부	이유
3과 4	✅ 대결함	같은 그룹 안에서 작은 번호가 홀수, 큰 번호가 짝수
4과 5	❌ 대결 안 함	다른 그룹에 속해 있어 대결 불가

3️⃣ 값이 줄어들 때마다 cnt++

라운드를 진행할 때마다 카운트를 하나씩 올립니다.
몇 번째 라운드인지 카운트를 저장해 두어야 합니다.

4️⃣ N이 0이 될 때까지 만나지 못하면 -1

만약 끝까지 진행했는데도 두 사람의 조건이 맞지 않는다면 -1을 출력해야 합니다.
즉, 참가자 수 N이 1이 될 때까지 만나지 못하면 -1입니다.

코드 전체 (내가 올린 것)

#include <iostream>
#include <cstring>
using namespace std;

int main(void)
{
    int N,n1,n2,cnt=1;

    cin>>N>>n1>>n2;

    while(N>0)
    {
        if(n2>n1)
        {
            if(n2-n1==1 && n1%2==1 && n2%2==0)
            {
                cout<<cnt<<endl;
                return 0;
            }
        }
        else
        {
            if(n1-n2==1 && n1%2==0 && n2%2==1)
            {
                cout<<cnt<<endl;
                return 0;
            }
        }

        if(n1%2==1)
            n1=(n1/2)+1;
        else if(n1%2==0)
            n1=(n1/2);
        if(n2%2==1)
            n2=(n2/2)+1;
        else if(n2%2==0)
            n2=(n2/2);
        N=N/2;
        cnt++;
    }

    cout<<-1<<endl;
    return 0;
}

개별 코드 설명

📌 입력 받기

cin>>N>>n1>>n2;

참가자 수 N과 김지민의 번호 n1, 임한수의 번호 n2를 입력받습니다.

📌 while문

while(N>0)

참가자 수가 0이 될 때까지 반복합니다. 더 이상 게임을 진행할 수 없을 때까지 진행됩니다.

📌 두 번호가 맞붙는지 확인

if(n2>n1)
{
    if(n2-n1==1 && n1%2==1 && n2%2==0)
    {
        cout<<cnt<<endl;
        return 0;
    }
}
else
{
    if(n1-n2==1 && n1%2==0 && n2%2==1)
    {
        cout<<cnt<<endl;
        return 0;
    }
}

• 두 사람의 번호 차이가 1이고
• 더 작은 쪽이 홀수이고, 더 큰 쪽이 짝수일 때
• 이 조건을 만족하면 그 라운드에서 맞붙게 됩니다.

📌 번호 갱신

if(n1%2==1)
    n1=(n1/2)+1;
else if(n1%2==0)
    n1=(n1/2);
if(n2%2==1)
    n2=(n2/2)+1;
else if(n2%2==0)
    n2=(n2/2);

다음 라운드에선 이긴 사람들만 남고 번호를 재배정 받습니다.
홀수면 (번호/2)+1, 짝수면 (번호/2)로 갱신됩니다.

📌 참가자 수 갱신

N=N/2;
cnt++;

참가자 수도 절반으로 줄어듭니다. 그리고 라운드 수를 1 증가시킵니다.

📌 못 만난 경우

cout<<-1<<endl;

끝까지 게임을 진행했지만 둘이 맞붙지 못했다면 -1을 출력합니다.

개선안

올려주신 코드도 잘 동작하지만, 아래와 같이 더 간결하게 작성할 수 있습니다.
핵심은 불필요한 조건 분기와 중복 코드를 없애는 것입니다.

개선된 코드

#include <iostream>
using namespace std;

int main() {
    int N, n1, n2, cnt = 1;

    cin >> N >> n1 >> n2;

    while (N > 1) {
        int small = min(n1, n2);
        int big = max(n1, n2);

        if (big - small == 1 && small % 2 == 1) {
            cout << cnt << endl;
            return 0;
        }

        n1 = (n1 + 1) / 2;
        n2 = (n2 + 1) / 2;
        N = (N + 1) / 2;
        cnt++;
    }

    cout << -1 << endl;
    return 0;
}

개선 포인트

• ✅ min, max를 활용해 작은 값과 큰 값을 구분
• ✅ 번호 갱신을 한 줄로 통일
• ✅ if-else 블록을 하나의 if로 단순화
• ✅ N도 (N+1)/2로 갱신해 안전하게 종료