[201125] 예상 대진표 - 2017 팁스타운(level2)

0. 문제 유형 : 규칙찾기

1. 문제 이해

programmers.co.kr/learn/courses/30/lessons/12985

코딩테스트 연습 - 예상 대진표

(1) 주요 요구사항

- 게임의 진행방식 : 1~N번까지 토너먼트로 진행, 한 라운드를 진출하면 다시 1~N/2로 번호 재배정

- 주어진 A번과 B번 참가자가 몇 번째 라운드에서 만나는지 return (서로 붙게 되기 전까지는 항상 이긴다고 가정)

 

(2) 제한사항

- N : 2^1 ~ 2^20의 자연수 → 부전승 발생X

- A, B : N이하의 자연수이며 둘은 같지 않음

 

 

2. 전략

(1) 번호 배정 규칙

- 번호가 짝수든, 홀수든 라운드를 진출해 번호를 받으면 " (x+1) / 2"의 값을 가진다!!

 

(2) 경쟁 대상

- k, k+1이 한 쌍이 되며, 이 때 k는 홀수이다.

- k와 k+1 둘 다 진출할 수 없으므로 둘이 붙으면 번호 배정 규칙에 따라 같은 수를 부여 받는다 ▶ 종료 조건으로 사용

 

 

3. 참고사항

X

 

 

4. 코드

class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer = 0;
        while(a != b){
            a = (a+1)/2;
            b = (b+1)/2;
            answer++;
        }
        return answer;
    }
}