백준 1057: 토너먼트 Python 풀이

백준 1057: 토너먼트 Python

문제

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입니다.

코드 전체 (원래 로직 기반)

N, n1, n2 = map(int, input().split())
cnt = 1

while N > 0:
    if n2 > n1:
        if n2 - n1 == 1 and n1 % 2 == 1 and n2 % 2 == 0:
            print(cnt)
            exit()
    else:
        if n1 - n2 == 1 and n2 % 2 == 1 and n1 % 2 == 0:
            print(cnt)
            exit()

    n1 = (n1 // 2) + (n1 % 2)
    n2 = (n2 // 2) + (n2 % 2)
    N //= 2
    cnt += 1

print(-1)

개별 코드 설명

📌 입력 받기

N, n1, n2 = map(int, input().split())

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

📌 while문

while N > 0:

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

📌 두 번호가 맞붙는지 확인

if n2 > n1:
    if n2 - n1 == 1 and n1 % 2 == 1 and n2 % 2 == 0:
        print(cnt)
        exit()
else:
    if n1 - n2 == 1 and n2 % 2 == 1 and n1 % 2 == 0:
        print(cnt)
        exit()

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

📌 번호 갱신

n1 = (n1 // 2) + (n1 % 2)
n2 = (n2 // 2) + (n2 % 2)

다음 라운드에선 이긴 사람들만 남고 번호를 재배정 받습니다.

📌 참가자 수 갱신

N //= 2
cnt += 1

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

개선안

불필요한 조건 분기와 중복 코드를 없앤 간결한 버전입니다.

개선된 코드

N, n1, n2 = map(int, input().split())
cnt = 1

while N > 1:
    small = min(n1, n2)
    big = max(n1, n2)

    if big - small == 1 and small % 2 == 1:
        print(cnt)
        exit()

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

print(-1)

개선 포인트

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