문제
N명이 참가하는 토너먼트에서 인접한 번호끼리 대결하고, 이긴 사람은 다음 라운드에 순서대로 새 번호를 받는다. 참가자가 홀수면 마지막 번호가 부전승한다. 김지민과 임한수가 몇 라운드에서 만나는지 구하라.
입력
첫째 줄에 N, 김지민의 번호, 임한수의 번호가 주어진다 (2 이상 100,000 이하).
출력
둘이 대결하는 라운드 번호를 출력한다. 만나지 않으면 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
16 8 9 | 4 |
풀이
매 라운드마다 두 사람의 다음 번호를 계산하여, 번호가 같아지는 라운드를 찾는다.
- 각 라운드에서 번호 x의 다음 라운드 번호는
x / 2 + x % 2(올림 나눗셈)이다 - 두 사람의 번호가 같아질 때까지 라운드를 증가시키며 반복한다
- 번호가 같아진 시점의 라운드가 정답이다
핵심 아이디어: 인접 번호끼리 대결하므로, 두 번호를 2로 나누어 올림하면 다음 라운드 번호가 된다. 같아지는 시점이 곧 대결 라운드이다.
코드
package com.ssafy.an.day199;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day169BOJ1057브루트포스 {
public static void main(String[] args) throws Exception {
StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());
int N = Integer.parseInt(st.nextToken());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int ans = 0;
while (A != B) {
A = A / 2 + A % 2;
B = B / 2 + B % 2;
ans++;
}
System.out.println(ans);
}
}복잡도
- 시간: O(log N) - 매 라운드마다 번호가 절반으로 줄어듦
- 공간: O(1)