[ 백준 1057 토너먼트 ] 문제 풀이(Java) - 시뮬레이션 문제

 

시뮬레이션 문제를 연습해보고자 푼 문제입니다!

 

백준 1057번 토너먼트 문제입니다.

 

 

문제 보기

https://www.acmicpc.net/problem/1057

1057번: 토너먼트

 

나의 풀이

 

처음 생각> 리스트를 이용하면 되지 않을까 했습니다. 리스트에 123...N까지 저장해두고 매 라운드마다 두 개씩 엮어서 하나씩 삭제해주면 자연스럽게 리스트의 인덱스를 통해 자리 이동이 되니까 가능하겠군! 했는데 해당 방법을 이용했더니 시간 초과가 발생했습니다.

 

처음 코드

//시뮬레이션 문제(리스트 이용)

package 백준;

import java.io.*;
import java.util.*;

public class N_1057 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String[] arr = br.readLine().split(" ");
			int N = Integer.parseInt(arr[0]);
			int kim = Integer.parseInt(arr[1]);
			int lim = Integer.parseInt(arr[2]);

			LinkedList<Integer> list = new LinkedList<Integer>();
			for (int i = 1; i <= N; i++)
				list.add(i);

			int roundNum = 0;
			while (list.size() != 1) {
				roundNum++;
				int flag = 0;
				
				if(list.size() % 2 == 1)
					flag = 1;
				for (int i = list.size() - 2; i >= 0; i -= 2) {
					if(flag == 1 && i == list.size() - 2)
						i--;
					if ((list.get(i) == kim && list.get(i + 1) == lim)
							|| (list.get(i) == lim && list.get(i + 1) == kim)) {
						System.out.println(roundNum);
						System.exit(0);
					} else if (list.get(i) == kim || list.get(i) == lim) {
						list.remove(i + 1);
					} else if (list.get(i + 1) == kim || list.get(i + 1) == lim) {
						list.remove(i);
					} else {
						list.remove(i + 1);
					}
				}
			}
			System.out.println(-1);

		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

 

당연한 것이 리스트의 원소를 계속해서 삭제해주는 방식이기 때문에 element의 추가적인 자리 이동이 필요해 시간 초과가 나는 것 같습니다.

 

 

그래서 다른 방법은 없을까 조금 고민해보았더니,,, 단순한 수학으로 풀 수 있는 문제였습니다. (나는 바보,,,,ㅠ)

 

예를 들어, 김미선과 임한수가 8과 9라고 하면

 

1라운드를 거치고 나면 미선이의 자리는 4, 한수의 자리는 5가 됩니다.

 

2라운드를 거치고 나면 미선이의 자리는 2, 한수의 자리는 3이 됩니다.

 

3라운드를 거치고 나면 미선이의 자리는 1, 한수의 자리는 2가 됩니다.

 

4라운드를 거치고 나면 미선이의 자리는 1, 한수의 자리는 1이 되어 둘이 같아지게 되어 정답은 4가 됩니다.

 

 

규칙이 보이시나요?

 

짝수인 경우에는 그냥 2로 나누어주고, 홀수인 경우에는 2로 나눈 것에 +1을 해주고

 

둘의 수가 같아질 때를 리턴해주면 됩니다.

 

 

코드

 

//시뮬레이션 문제

package 백준;

import java.io.*;
import java.util.*;

public class N_1057 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String[] arr = br.readLine().split(" ");
			int N = Integer.parseInt(arr[0]);
			int kim = Integer.parseInt(arr[1]);
			int lim = Integer.parseInt(arr[2]);

			int roundNum = 0;
			while (!(kim == 1 && lim == 1)) {
				roundNum++;

				// 김지민
				if (kim % 2 == 0)
					kim /= 2;
				else
					kim = kim / 2 + 1;

				// 임한수
				if (lim % 2 == 0)
					lim /= 2;
				else
					lim = lim / 2 + 1;

				if (kim == lim) {
					System.out.println(roundNum);
					System.exit(0);
				}
			}
			System.out.println(-1);
			
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

 

결과

채점결과 pass!

 

후기

• 처음에 kim /= 2 + 1; 로 코딩해서 "틀렸습니다"가 떴다. 문법에 주의하자! (이거는 3으로 kim을 나눈다는 의미,,,)