문제
김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.
마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.
링크 참조
풀이 설명
입력 받은 사람 수에서 지민이와 한수가 몇 단계에서 만나는 지 출력하는 것이다.
예를 들어, N이 16이면 1부터 16번의 참가자가 있고 지민이가 8번, 한수가 9번이라고 생각하면
1-2 / 3-4 / 5-6 / 7-8 / 9-10 / 11-12 / 13-14 / 15-16 으로 1단계 경기를 하고 (지민 한수는 무조건 이김 !!)
1-3 / 5-지민 / 한수-11 / 13-15 로 2단계가 진행된다. (홀수번이 이겼다고 가정)
1-지민 / 한수-13 로 3단계가 진행되고
지민-한수 로 마지막 4단계가 진행되기 때문에 출력은 4가 되면 된다.
나의 방식은 몫과 나머지를 이용했다. 1번부터 16번이라고 생각하지 않고 2번부터 17번이라고 생각했다.
그렇게 되면, 2-3 / 4-5 / 6-7 / ... 16-17 이 되는데, 경기 하는 묶음끼리는 2로 나눴을 떄의 몫이 같다는 관계가 있다.
N명의 참가자가 있다면 경기가 진행될 수록 N/2 -> (N/2)/2 -> ((N/2)/2)/2 .. 이런식으로 점차 반으로 줄어간다.
따라서 참가자가 1명 이상 있을 때까지 반복하는 코드를 구현했다.
코드
N, jimin, hansu = map(int,input().split())
jimin += 1
hansu += 1
count = 1
while N > 1:
if jimin//2 == hansu//2:
break
else:
N = N//2
hansu //= 2
jimin //= 2
hansu += 1
jimin += 1
count += 1
print(count)위에서 설명했던 것처럼 N이 1보다 클 때까지만 반복한다 (= 참가자가 1명 이상일 때까지만)
그리고 한수와 지민이의 2로 나누었을 때 몫이 같다면 만난 것을 의미하기 때문에 while문을 탈출한다.
몫이 다르다면, 둘이 만난 것이 아니므로 경기 수를 반으로 줄이고, 지민이와 한수의 값도 2로 나눈 몫으로 대체하고 다시 1씩 더해준다.
python에서 몫만을 구해주는 연산자는 // 이다.
ex) 5//2 = 1 의 결과가 나온다.
💌
후기
예제 입출력은 다 맞았다고 뜨는데 실패합니다가 계속 떠서 반례를 전부 넣어 실행해봐도 맞는 결과가 나왔었다.
알고보니 break 전에 print문을 넣어놔서 그랬다.
print()하고 break 하면 뭐가 다른가..? 하하
아직도 정확한 원인을 잘 모르긴 하지만 아무튼 그거 빼고는 어려움은 없었다.
