알고리즘 #0003

• 문제 링크: 바로가기 (클릭)

I. 문제 상황

1. 초기 코드 작성

• 주어진 문제에 따라 $2^n$명이 토너먼트를 거쳐 a와 b가 만나기 위한 경기 횟수를 구해야 한다. (a와 b는 경기에서 만나기 전까지 항상 승리한다고 가정)
• 10번이 이길 경우 다음 경기에서는 5번을, 5번이 이길 경우 그 다음 경기에서는 3번을 받는다.
• 따라서 아래의 [코드 1]처럼 현재 번호가 짝수일 경우 다음 경기에서 2로 나누고, 현재 번호가 홀수일 경우 현재 번호에 1을 더한 후 2로 나누는 로직을 구현하였다.
• [코드 1] 처음 작성한 코드 답안

import java.util.*;
class Solution {
    public int solution(int n, int a, int b) {
        int answer = 1;
        while (n > 1) {
            if (Math.abs(a - b) == 1) {
                break;
            }
            if (a%2 == 1) {
                a++;
            }
            if (b%2 == 1) {
                b++;
            }
            answer++;
            a /= 2;
            b /= 2;
            n /= 2;
        }
        return answer;
    }
}

2. 실행 결과

• 하지만, 아래의 [결과 1]에서처럼 오류가 발생하였다.
• [결과 1]
  

II. 문제 분석

1. 테스트 케이스 분석

• 기존 [코드 1]에서, a가 4이고 b가 5일 경우 경기를 한 번 더 진행해야 하는데 if (Math.abs(a - b) == 1) 조건문에서 바로 break된다.
• 따라서 [코드 2]와 같이 조건문을 추가하였다.
• [코드 2] 수정한 코드
  

2. 실행

• [결과 2]