[프로그래머스] 12985번 - 예상 대진표 (Java)

출처: 프로그래머스 코딩테스트 연습

https://school.programmers.co.kr/learn/courses/30/lessons/12985

프로그래머스

---

 

문제

 

 

풀이

입출력 예를 살펴보면 N=8이기 때문에 1, 2, 3, 4, 5, 6, 7, 8 번의 참가자가 게임을 진행한다.

 

토너먼트 형식이기 때문에 1번 - 2번 / 3번 - 4번 / 5번 - 6번 / 7번 - 8번 끼리 진행된다.

1라운드가 끝나면 번호는 다시 1부터 배정이 되기 때문에 1, 2, 3, 4번으로 배정이 될 것이다.

 

이때 규칙을 찾을 수 있는데, 현재 번호에 1을 더하고 2로 나눈 몫이 다음 라운드에 배정 받을 번호가 된다는 것이다.

다음 라운드 배정 번호	1번	2번	3번	4번
현재 라운드 번호	1번 : (1 + 1) / 2 = 1번 2번 : (2 + 1) / 2 = 1번	3번 : (3 + 1) / 2 = 2번 4번 : (4 + 1) / 2 = 2번	5번 : (5 + 1) / 2 = 3번 6번 : (6 + 1) / 2 = 3번	7번 : (7 + 1) / 2 = 4번 8번 : (8 + 1) / 2 = 4번

위 표처럼 1, 2번의 경우 다음 라운드에서는 1번을, 3, 4번의 경우 2번을 배정받게 될 것이다.

 

4번과 7번은 서로 붙게 될 때까지 항상 이기기 때문에 항상 번호를 배정 받게 될 것이다.

따라서 4번과 7번이 서로 붙을 때까지 == 4번과 7번이 다음 라운드에 배정 받게 될 번호가 같아질 때까지, 다음 라운드에 배정 받게 될 번호를 반복적으로 구하고 라운드 횟수를 카운트 해준다.

 

말로 하려니 복잡하지만 코드를 보면 훨씬 이해가 쉬울 것이다!

 

 

 

소스코드

import java.util.*;

class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer = 0; // 라운드 횟수

	// 반복문 한 번이 라운드 한 번
        // a와 b가 같아지면 즉, a와 b가 붙게 되면 반복문 중단
        while(a != b){
            // a와 b의 다음 라운드에 배정 받게 될 번호를 구한다
            a = (a + 1) / 2;
            b = (b + 1) / 2;
            answer ++;
        }
        
        return answer;
    }
}