예상 대진표

작성일: 2024-11-04

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12985

접근 방식

N은 최대 백만까지다. 따라서 이 문제는 완전탐색이 아닌, 패턴 분석을 통해서 문제를 해결해야 한다.

주어진 예제를 보면, 8번까지 존재하고 A=4, B=7로 주어진다.
A와 B는 무조건 이기는 것으로 보고, 둘이 만나게 되는 라운드를 구해야한다.

A는 3번과 만나게 되고, 이겨서 2번을 배정받는다.
B는 8번과 만나게 되고, 이겨서 4번을 배정받는다.

다시 라운드가 시작되고,

A는 1번과 만나서 이겨서 1번을 배정받고
B는 3번과 만나서 이겨서 2번을 배정받는다.

배정을 받는 과정에서 패턴을 확인할 수 있다.

무조건 이기기 때문에 번호를 배정받는다. 이 과정에서 내가 홀수라면 번호/2 + 1을 배정받는다.
짝수는 번호/2를 배정 받는다.

따라서 이 과정을 a와 b가 서로 만나는 경우까지 반복하면 정답을 알 수 있다.

여기서 주의할 점은, a=2 b=3의 경우 만나는 경우의 수가 아니라는 것이다.
a의 짝수 여부를 판단해서 짝수인 경우 b에서1을 더했을 때 a인 경우와
홀수의 경우, a에서 1을 더했을 때 b인 경우에만 반복을 빠져나와야 한다.

결과

소스 코드

import java.util.*;

class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer = 0;
        while(true){
            answer++;
            if(a%2==0 && a==b+1){
                break;
            }else if(a%2!=0 && a+1==b){
                break;
            }
            if(a%2!=0) a=a/2 + 1;
            else a/=2;
            if(b%2!=0) b=b/2 + 1;
            else b/=2;

        }

        return answer;
    }
}

다른 접근 방식

없음.

알게 된 점

숫자가 터무니 없게 크고, dfs로 풀 수 없다고 판단되는 경우에는

패턴을 파악할 수 있어야한다.