백준_1057 토너먼트

링크 https://www.acmicpc.net/problem/1057

1057번: 토너먼트

 

접근

경기 대진표를 그려본다

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1 3 5 8 9 11 13 15

1 8 9 13

8 9

 

8번과 9번의 번호를 추척하면 규칙을 찾을 수 있다

8 -> 4 -> 2 -> 1

9 -> 5 -> 3 -> 2 -> 1

 

9 - 5 = 4 = 9/2

5 - 3 = 2 = 5/2

...

다음 라운드로 진출할때는 번호 - (번호/2) 번의 숫자가 붙는것을 알 수 있다

 

두 선수의 번호가 같아질때까지

a = a-(a/2)

b = b-(b/2)

round++

 

위 공식을 코드로 그대로 옮기면 된다

 

#include <iostream>

using namespace std;

int main(void){
    int n, p1, p2, round;
    scanf("%d %d %d", &n, &p1, &p2);
    round = 0;
    while(p1!=p2){
        p1 = p1-(p1/2);
        p2 = p2-(p2/2);
        round++;
    }
    printf("%d \n", round);
}