[백준 / BOJ] 28457번 : Every? Only One's Marble (JAVA)

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

28457번: Every? Only One's Marble

시뮬레이션

정말 정직한 시뮬레이션 문제이기 때문에, 사실 문제를 제대로 읽고 덤볐다면 좀 더 빨리 맞출 수 있지 않았을까 하는 아쉬움이 남는다. 이번 문제는 코드 풀이보다는 어째서 틀렸는지를 적어두는 게 나을 것 같다.

 

** 주의 :

문제에서는 첫 칸이 1, 마지막 칸이 4n - 4로 정해져 있지만 개인적으로 이렇게 계산하는 게 헷갈려서 첫 칸은 0, 마지막 칸은 4n - 5 로 문제를 풀었다. 

 

 

1. 같은 주사위를 냈을 때 무인도를 바로 빠져나가는 게 아니다.

문제 이해를 잘못해서, 같은 숫자가 나오자마자 무인도에서 빠져나올 수 있다고 생각했다. 하지만 읽어보면 같은 숫자가 나오는 것은 '탈출 조건'이고, 실제로 움직이는 것은 그 다음 주사위 수만큼이다. 이것 때문에 첫 번째 예제에서 자꾸 전체 땅을 사지 못해 LOSE를 출력했었다.

 

첫번째 예제를 사용하여 설명하자면, 13번째 (1, 1) 조합으로 이동하면 무인도에 갇히게 된다. 그 다음 주사위는

[14] 2 3 // 무인도에 갇힌 후 첫 번째 주사위
[15] 6 3 // 무인도에 갇힌 후 두 번째 주사위
[16] 5 5 // 무인도에 갇힌 후 세 번째 주사위
[17] 2 1

이렇게 나온다. (2, 3)과 (6, 3)은 두 주사위의 수가 다르니 당연히 탈출이 안된다. 16번째 (5, 5)으로 드디어 탈출이 가능해졌다! 하지만 이 때 5 + 5 = 10 칸을 움직이는 게 아니라, 그 턴은 탈출이 가능해진 것으로 만족하고, 다음 17번째 (2, 1) 주사위로 움직인다. 2 + 1 = 3 칸을 움직이는 것이다.

 

2. 시작을 지나간다고 무조건 원래 값보다 작아지지 않는다.

이게 무슨 소리냐면, 나는 처음에 "시작 칸을 지나간 것을 어떻게 찾아낼까?"의 답으로

if (next < current)

를 생각했다. 한 바퀴를 돌아서 왔기 때문에 전진했는데도 불구하고 전 값보다 작아진다고 생각했던 것이다. 물론 n이 큰 경우에는 이럴 수 있다. 주사위 두 개를 합쳐서 최대 12밖에 만들지 못하니까. 하지만 n이 3처럼 작은 숫자라면 한 바퀴를 돌고도 원래 값보다 더 앞서 나갈 수 있다! 따라서 위와 같은 조건은 집어치우고

if (next >= N) {
	S += W;
    next -= N;
}

로 코드를 바꾸었다. 그리고 이를 통해 런타임 에러 (ArrayIndexOutOfBounds) 가 나고 만다.

 

3. 숫자에 따라 한 바퀴 이상을 돌 수 있다.

2번을 깨달았으면서 3번을 간과한 건 아쉬운 실수였다. 다음과 같은 경우에 주사위 한 번으로 여러 바퀴를 돌게 된다.

n = 3
현재 위치 = 7

이번 턴의 주사위 = (6, 6)

 

앞서 작성한 코드에서는 7 + 6 + 6 = 19 를 하고, N인 8보다 크니 19 - 8 = 11 번째 칸으로 가라 했을 것이다. 여전히 N보다 크기 때문에 ArrayIndexOutOfBounds가 나올 수 밖에 없다. 따라서 

if(next >= N) {
	S += W * next / N;
    next %= N;
}

으로 바꾸었다. 한 가지 더 바뀐 것은 시작 칸을 찍을 때 받을 월급이다. 위와 같은 경우 두 바퀴를 돌면서

 

7(시작) -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 0 -> 1 -> 2 -> 3

 

와 같이 당연히! 시작을 두 번 찍게 된다. 따라서 월급도 두 번 줘야 하는 것이다. 이걸 바로 깨달았으면 좋았을텐데, 두 바퀴를 돌 수 있다! 라는 생각을 하자마자 신나서 next만 고치고 제출했다가 또다시 '틀렸습니다'를 받아 아쉽다.

 

전체 코드

// 시간 : 96ms
// 메모리 : 13056KB
public class Main {

	static int N;
	static long S;
	static int W;
	static int START;
	static int ILAND;
	static int LAND;
	static int SOCIAL;
	static int S_MONEY;
	static int UNIVERSE;
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		N = 4 * n - 4;
		S = Long.parseLong(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		int G = Integer.parseInt(st.nextToken());
		
		Queue<int[]> goldkey = new LinkedList<>();
		
		for (int i = 0; i < G; i++) {
			st = new StringTokenizer(br.readLine());
			int op = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			goldkey.offer(new int[] {op, x});
		}
		
		int[] map = new int[N];
		
		START = 0;
		ILAND = n - 1;
		SOCIAL = 2 * n - 2;
		UNIVERSE = 3 * n - 3;
		LAND = 0;
		
		for (int i = 0; i < N; i++) {
			if(i == START || i == ILAND || i == SOCIAL || i == UNIVERSE) {
				map[i] = -2;
				continue;
			}
			st = new StringTokenizer(br.readLine());
			char loc = st.nextToken().charAt(0);
			if(loc == 'G') {
				map[i] = -1;
			} else {
				int cost = Integer.parseInt(st.nextToken());
				map[i] = cost;
				LAND++;
			}
		}
		int I = Integer.parseInt(br.readLine());
		
		int l = 0;
		int iland = 0;
		S_MONEY = 0;
		
		for (int t = 0; t < I; t++) {
			st = new StringTokenizer(br.readLine());
			int d1 = Integer.parseInt(st.nextToken());
			int d2 = Integer.parseInt(st.nextToken());
			
			if(l == ILAND) {
				if(d1 == d2) {
					iland = 3;
					continue;
				} else if(iland == 3) {
					iland = 0;
				} else {
					iland++;
					continue;
				}
			} 
			
			int next = l + d1 + d2;
			
			if(next >= N) {
				S += W * next / N;
				next %= N;
			}
			
			l = after_move(next, l, map, goldkey);
		}
		
		if(LAND == 0) System.out.println("WIN");
		else {
			System.out.println("LOSE");
		}
	}

	
	static int after_move(int next, int l, int[] map, Queue<int[]> goldkey) {
		
		if(next == START) {
			return START;
		}
		
		if(next == SOCIAL) {
			S += S_MONEY;
			S_MONEY = 0;
			return next;
		}
		
		if(next == UNIVERSE) {
			S += W;
			return START;
		}
		
		if(map[next] > 0) {
			if(S >= map[next]) {
				S -= map[next];
				map[next] = 0;
				LAND--;
			}
		} else if(map[next] == -1) {
			int[] cur = goldkey.poll();
			goldkey.offer(cur);
			int op = cur[0];
			if(op == 1) {
				S += cur[1];
			} else if(op == 2) {
				S -= cur[1];
				if(S < 0) {
					System.out.println("LOSE");
					System.exit(0);
				}
			} else if(op == 3) {
				S -= cur[1];
				S_MONEY += cur[1];
				if(S < 0) {
					System.out.println("LOSE");
					System.exit(0);
				}
			} else {
				l = next;
				next += cur[1];
				if(next >= N) {
					S += W * next / N;
					next %= N;
				}
				return after_move(next, l, map, goldkey);
			}
		}
		
		return next;
	}
}