[BaekJoon] 1057 토너먼트

1.  문제 링크

2.  문제

요약

• N명이 참가하는 토너먼트 대회에서 김지민과 임한수가 몇 라운드에 대결하는지 구하는 문제입니다.
• 만약 참가자가 홀수명이라면 마지막 번호를 가진 참가자는 다음 라운드로 진출합니다.
• 1번과 2번이 진행해서 이긴 참가자가 다음 라운드에서 1번, 3번과 4번이 진행해서 이긴 참가자가 다음 라운드에서 2번,... 이런 방식으로 라운드가 진행됩니다.
• 입력: 첫 번째 줄에 참가자 수 N과 1라운드에서 김지민의 번호와 임한수의 번호가 주어집니다.
• 출력: 김지민과 임한수가 대결하는 라운드 번호를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public int getRound(String input) {
		StringTokenizer st = new StringTokenizer(input);
		int num = Integer.parseInt(st.nextToken());
		int kim = Integer.parseInt(st.nextToken());
		int lim = Integer.parseInt(st.nextToken());
		int round = 1;
		for(int i = num; i >= 1; i /= 2) {
			if(((kim + 1 == lim) && (kim % 2 == 1)) || ((lim + 1 == kim) && (lim % 2 == 1))) {
				return round;
			}
			kim = kim / 2 + kim % 2;
			lim = lim / 2 + lim % 2;
			round++;
		}
		return round;
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input = br.readLine();
		br.close();
		Main m = new Main();
		bw.write(m.getRound(input) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

1. 두 사람이 라운드에서 만나려면 한 명이 홀수, 한 명은 짝수여야 하고 홀수가 짝수보다 1 작아야 합니다.
2. 라운드는 진행될 때마다 라운드 참가 인원이 반 정도로 줄어들기 때문에 이를 이용하여 라운드가 끝날 때까지 두 사람의 번호를 계산합니다.
3. 홀수 번호는 다음 라운드에서 현재 번호를 2로 나눈 값에 1을 더한 번호가 되고 짝수는 다음 라운드에서 현재 번호를 2로 나눈 값이 되기 때문에 이를 이용하여 다음 라운드에서의 두 사람의 번호를 구합니다.
4. 3번의 방법으로 계속 두 사람의 다음 라운드에서의 번호를 구하고 1번 조건을 만족했을 때의 라운드 번호를 출력합니다.