Baekjoon - 1057

문제

Solved.ac Silver 4

1, 2 차시도

배열을 이용하여 시도하였으나 시간초과가 나왔다.

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");

		int participantCount = Integer.parseInt(split[0]);
		int myNumber = Integer.parseInt(split[1]);
		int competitionNumber = Integer.parseInt(split[2]);

		int[] data = new int[participantCount + 2];
		for (int i = 1; i < participantCount + 1; i++) {
			data[i] = i;
		}
		data[myNumber] = -1;
		data[competitionNumber] = -1;

		int count = 0;

		while (true) {
			count++;

			for (int i = 1; i <= participantCount; i = i + 2) {
				if (data[i] == data[i + 1]) {
					System.out.println(count);
					return;
				}
			}
			data[myNumber] = myNumber;
			if (myNumber % 2 == 1) { //홀수
				myNumber = myNumber / 2 + 1;
			} else { //짝수
				myNumber = myNumber / 2;
			}
			data[myNumber] = -1;

			data[competitionNumber] = competitionNumber;
			if (competitionNumber % 2 == 1) {
				competitionNumber = competitionNumber / 2 + 1;
			} else {
				competitionNumber = competitionNumber / 2;
			}
			data[competitionNumber] = -1;

			if (participantCount % 2 == 1) {
				participantCount++;
			}
			participantCount = participantCount / 2;

		}

	}
}

시간초과

3차시도

2로 계속 나누다 보면 1이된다는 사실을 발견하고 이를 통해 해결하였다

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");

		int participantCount = Integer.parseInt(split[0]);
		int myNumber = Integer.parseInt(split[1]);
		int competitionNumber = Integer.parseInt(split[2]);

		int count = 0;

		while (myNumber != competitionNumber) {
			count++;
			if (myNumber % 2 == 1) { //홀수
				myNumber = myNumber / 2 + 1;
			} else { //짝수
				myNumber = myNumber / 2;
			}

			if (competitionNumber % 2 == 1) {
				competitionNumber = competitionNumber / 2 + 1;
			} else {
				competitionNumber = competitionNumber / 2;
			}

		}
		System.out.println(count);
	}
}

성공