백준 1057 : 토너먼트 (자바)
문제 바로 가기
https://www.acmicpc.net/problem/1057
접근 방법
수학적인 규칙을 찾으면 될 것 같다는 생각은 했지만, 수학적 규칙을 빠르게 찾아내지 못하는 편이라 고민을 좀 했다. 수학적인 규칙을 찾았다면 코드를 작성하는 것은 빠르게 끝낼 수 있다.
Step 01. 규칙 찾기
라운드마다 참가자의 번호는 갱신된다. 따라서 누가 토너먼트에서 이겼는지 정확한 번호를 아는 것은 크게 의미가 없다. 라운드마다 번호를 매기는 순서는 처음 번호의 순서를 유지한다는 규칙이 있기 때문에 이 점을 고려하여 규칙을 생성할 수 있다.
1과 2는 함께 대결하게 되고, 다음 라운드에서 이 둘 중 하나가 다음 라운드에 진출했을 때 진출한 사람은 다시 참가 번호 1번을 얻게 된다. 이때의 규칙을 살펴보면 참가자의 다음 라운드 번호는 현재 번호를 2로 나누었을 때 몫이 된다. 즉, 이때의 규칙은 (number + 1) / 2 와 같이 표현할 수 있다. 이때 이 규칙은 N이 짝수가 아닌 홀수여도 동일하게 적용할 수 있는 규칙이다.
이렇게 김지민과 임한수의 번호에 (number + 1) / 2 계산식을 계속 적용하다가 만약 이 둘의 값이 동일해지면 같은 라운드에서 만나는 것이기 때문에 계산을 멈추고 라운드 값을 반환하면 된다.
이러한 규칙만 생각하면 간단하게 아래와 같이 처리할 수 있다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int kim = Integer.parseInt(st.nextToken());
int lim = Integer.parseInt(st.nextToken());
int round = 0;
// 김지민과 임한수가 같은 라운드에서 만날 때까지 반복한다.
while (kim != lim) {
round++;
// 라운드마다 번호는 갱신된다.
kim = (kim + 1) / 2;
lim = (lim + 1) / 2;
}
// 결과 출력
bw.write(String.valueOf(round));
bw.newLine();위와 같이 작성하고 제출해도 정답 처리가 된다. 그런데, 위의 풀이에는 말장난 같은 오류가 있는데, 바로 예외 처리가 안 되어 있다는 점이다.
Step 02. 예외도 처리해주기
서로 대결하지 않을 때는 -1을 출력해야 한다고 하는데, 위의 풀이에는 -1을 출력할 수 있는 부분이 없다. 그런데, 문제를 다시 읽어보면, 굳이 예외를 처리해 주는 것이 필요 없다는 것을 알 수 있다.
"서로 대결하지 않을 때"라는 조건은 사실상 모든 참가자가 토너먼트를 통해서 최종적으로 한 명의 승자가 결정되는 구조라면, 두 참가자가 대결하지 않는 경우는 없을 것이다. 따라서 기본적으로 토너먼트가 계속 진행된다면 두 참가자는 언젠가 반드시 만나게 되어 있다.
이러한 이유로 대결하지 않을 때 -1을 출력하는 것이 없어도 정답 처리가 되지만, 그럼에도 요구사항을 명확하게 맞출 수 있도록 예외 처리를 추가해 보자.
최대 라운드 수 계산하기
토너먼트의 최대 라운드 수는 참가자 수 N이 주어졌을 때 모든 참가자가 최종적으로 한 명이 남을 때까지 몇 번의 라운드가 진행되는지를 의미한다. 토너먼트 대결의 구조와 문제의 조건에 따라서 김지민과 임한수는 무조건 만나게 되지만, 만약 절대 만날 수 없는 상황이 있다면 최대 라운드 수를 정해두고, 최대 라운드에 도달할 때까지 만나지 못했다면 라운드 번호를 갱신하는 작업을 멈춰야 한다.
최대 라운드 수 계산은 이진 트리에서 리프 노드들이 서로 대결하여 루트 노드에 도달하는 과정과 유사하다.
1. 이진 트리 구조
토너먼트는 라운드마다 참가자가 반으로 줄어든다. 예를 들어 8명의 참가자가 있을 때
1라운드 후 : 8명이 4명으로 줄어듦
2라운드 후 : 4명이 2명으로 줄어듦
3라운드 후 : 2명이 1명으로 줄어듦
이처럼 참가자 수가 2의 거듭제곱일 때, 필요한 라운드의 수는 `log_2N`이 된다.
2. 일반적인 경우
그런데 항상 참가자 수가 반드시 2의 거듭제곱이 아닐 수 있다. 예를 들어 6명의 참가자 있다면
1라운드 후 : 6명이 3명으로 줄어듦.
2라운드 후 : 3명이 2명으로 줄어듦(부전승 발생 가능).
3라운드 후 : 2명이 1명으로 줄어듦.
이 경우에도 결국 밑이 2인 `log_2N`에 해당하 라운드가 필요하지만 올림 처리가 필요하다. 왜냐하면 N이 2의 거듭제곱이 아니라면 로그값에 소수점이 생기기 때문이다. 따라서 Math.log(N) / Math.log(2) 로 값을 구하고 Math.ceil 을 사용해서 올림 처리하면 된다.
결과적으로 최대 라운드 수는 아래와 같이 구할 수 있다.
int maxRounds = (int) Math.ceil(Math.log(N) / Math.log(2));
Step 03. 전체 코드 작성하기
앞서 문제 풀이에 필요한 로직도 살펴보았고, 예외 처리에 필요한 계산식도 모두 구했다. 이를 모두 적용한 풀이는 아래와 같다.
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입력과 출력을 위한 BufferedReader와 BufferedWriter 초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 입력을 한 줄 읽고 StringTokenizer를 사용해 공백으로 구분된 숫자들을 토큰화
StringTokenizer st = new StringTokenizer(br.readLine());
// 첫 번째 토큰은 N, 두 번째는 김지민의 번호, 세 번째는 임한수의 번호
int N = Integer.parseInt(st.nextToken());
int kim = Integer.parseInt(st.nextToken());
int lim = Integer.parseInt(st.nextToken());
// 현재 라운드 번호를 0으로 초기화
int round = 0;
// 최대 라운드 수는 N의 로그2값 올림 처리
int maxRounds = (int) Math.ceil(Math.log(N) / Math.log(2));
// 김지민과 임한수가 같은 라운드에서 만날 때까지 반복
while (kim != lim && round < maxRounds) {
// 라운드 번호 증가
round++;
// 김지민과 임한수의 번호를 다음 라운드의 번호로 갱신
kim = (kim + 1) / 2;
lim = (lim + 1) / 2;
}
// 결과를 출력
if (kim == lim) {
bw.write(String.valueOf(round));
} else {
bw.write(String.valueOf(-1));
}
bw.newLine();
// BufferedReader와 BufferedWriter 닫기
br.close();
bw.close();
}
}