[백준] 5546번 : 파스타 - JAVA[자바]

• Algorithm Problem

• Solving

1. 연속으로 3일이 되는 경우는 없다. 
2. 오늘이 연속된 맛 2일차라면, 해당 맛의 그 전날 1일차인 경우의 수와 같다.
3. 오늘이 맛 1일차라면, 다른 두 맛의 1, 2일차의 경우의 수의 합과 같다.
4. 순회 경우는 마지막날 기준 (3가지 맛) * (1일차 인지, 2일차인지)의 6가지의 총합이다.
5. 1일차를 무작정 1/0으로 초기화 할 수 없다. 고정된 2, 3일차를 고려해야한다.

예제 1
5 3 -- day, 지정일자
3 1 -- 3일차는 1번 맛
1 1 -- 1일차는 1번 맛
4 2 -- 4일차는 2번 맛
x o x x o -- x : 고정 o : 변화
1 2 1 2 1
1 2 1 2 2 -- 연속 2일차인 경우
1 2 1 2 3
1 3 1 2 1
1 3 1 2 2 -- 연속 2일차인 경우
1 3 1 2 3
예제 1 result 
1번 맛 : n/n 0/n 2/0 n/n 2/0 -- 4일차가 2로 고정이어서 연속 1일차만 2가지 경우가 있다.
2번 맛 : n/n 1/0 n/n 2/0 0/2 -- 4일차가 2로 고정이어서 연속 2일차만 2가지 경우가 있다.
3번 맛 : n/n 1/0 n/n n/n 2/0 -- 4일차가 2로 고정이어서 연속 1일차만 2가지 경우가 있다.

3일이 고정되어있어, 2일차와 5일차의 경우만 확인하면 된다. 하루로 예제를 바꿔서 생각해보자.

테스트 예제
5 1 -- 5일중 하루만 지정된 맛, 2일차만 1번 맛
2 1
테스트 예제 result : 60
--------지정--------------
1 : n/n 2/1 0/2 6/0 16/6 
2 : n/n n/n 3/0 5/3 14/5 
3 : n/n n/n 3/0 5/3 14/5 

1일차는 2일차가 1번맛으로 정해져 있고, 3일차는 안정해져 있기 때문에, 1일차는 세가지 맛 모두 1/0으로 작성이 가능하다. 1/0의 의미는 해당 맛이 1일차 조건인 경우/2일차 조건인 경우이다. 3일차가 고정이 아니기때문에 1/0으로 채울 수 있다는 것을 다시 한번 생각하자.

2일차에서는 1번 맛이 1일차 경과인 수는 그 전날 맛이 2또는 3번 맛인 경우의 합이기 때문에, 1+0+1+0 = 2 이다. 1번 맛이 2일 차인 경우의 수는 그 전날 맛이 1일때 1일차인 경우의 수 1과 같다.

3일차는 1번 맛이 1일차일 경우는 0이다. 이미 앞서 2일차가 1번맛으로 정해져 있기 때문에 불가능하다. 1번 맛이 2일차인 경우는 그 전날 1번맛이 1일차인 경우와 같은 2이다. 2번맛과 3번 맛은 각각 2일차 맛이 1로 정해져있기 때문에 2일차인 경우의 수는 0 이고, 1일차인 경우의 수는 그 전날 해당 맛이 아닌 경우의 수의 총합(1번맛 고정) 2+1 = 3이다.

4일차는 1번 맛일 경우의 수는 그 전날의 2, 3번맛 경우의 수의 총합 3+0+3+0이고, 2일차인 경우의 수는 그 전날의 1일차인 경우의 수 0 과 같다. 2, 3번 맛은 각각 1일차의 경우의 수는 그 전날 해당 맛이 아닌 경우의 수 0+2+3+0 = 5 이고, 2일차인 경우의 수는 그전날 1일차인 경우의 수 3과 같다.

5일차는 1번 맛의 경우 그 전날의 2, 3번 맛의 경우의 수 총합 5+3+5+3 = 16이고, 2일차인 경우의 수는 그전날 1일차인 경우의 수 6과 같다. 2,3번 맛은 각각 1일차인 경우의 수는 그 전날 해당 맛이 아닌 경우의 수 총합 6+0+5+3 = 14이고, 2일차인 경우의 수는 그 전날이 1일차인 경우의 수 5와 같다.

위 내용을 바탕으로 재귀문을 구성하면 다음과 같다.

	private static int recur(int cur, int sel, int cnt) {
		if (arr[cur] != -1 && arr[cur] != sel) // cur : 현재일자, sel : 선택된 맛, cnt : 일차
			return 0; // 맛이 정해진 날짜인데, 해당 맛이 아닌경우는 경우의 수 변화 없음
		if (cur == 1) // N일차 부터 시작해서 1일차까지 내려왔을 때, 
			return cnt == 0 ? 1 : 0; // cnt - 0 : 1일차 인 경우 1, 1 : 2일차인 경우는 불가 0
		if (dp[cur][sel][cnt] != null)
			return dp[cur][sel][cnt]; // 이미 계산된 값이면 메모이제이션으로 반환
		dp[cur][sel][cnt] = 0; // Integer로 배열을 만들면 초기화 없이 null비교가 가능하다.
		int tmp = 0; 
		if (cnt == 0) { // 방문 했을 때 1일차라면, 가능한 경우의 수는
			for (int i = 0; i < 3; i++) { // i는 전날 선택할 맛
				if (i == sel) // 현재 sel이 1일차이기 때문에, 전날 맛이 같을 수 없다.
					continue;
				tmp = (tmp + recur(cur - 1, i, 0) + recur(cur - 1, i, 1)) % MOD;
			} // 해당 맛이 1일차 일때 가능한 경우의 수는 cur-1 하루전날 다른 맛 경우의 수의 총합
		} else
			tmp = recur(cur - 1, sel, 0); // 해당 맛이 2일차면 전날 1일차(0)과 경우의 수가 같다.
		return dp[cur][sel][cnt] = tmp; // 메모이제이션
	}

중점 사항은 해당맛이 3일 연속 불가능 하기 때문에 1,2일차 여부 와 3가지 맛을 곱한 총 6번의 순회를 시켜야 하며, 하루씩 리프트리로 이동하기때문에 메모이제이션이 없다면 10회만 반복해도 시간초과가 날 것이다. 

반응형

• Full Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Day81BOJ5546파스타 {
	static final int MOD = 10_000;
	static int N, K, ans;
	static int[] arr;
	static Integer[][][] dp;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = ip(st.nextToken());
		K = ip(st.nextToken());
		ans = 0;
		arr = new int[N + 1];
		Arrays.fill(arr, -1);
		dp = new Integer[N + 1][3][2];
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			arr[ip(st.nextToken())] = ip(st.nextToken()) - 1;
		}
		for (int i = 0; i < 3; i++) { // 맛
			for (int j = 0; j < 2; j++) { // 연속
				ans += recur(N, i, j);
//				System.out.println("result : " + recur(N, i, j));
//				print(dp);
			}
		}
		System.out.println(ans % MOD);
		br.close();
	}

	private static int recur(int cur, int sel, int cnt) {
		if (arr[cur] != -1 && arr[cur] != sel)
			return 0;
		if (cur == 1)
			return cnt == 0 ? 1 : 0;
		if (dp[cur][sel][cnt] != null)
			return dp[cur][sel][cnt];
		dp[cur][sel][cnt] = 0;
		int tmp = 0;
		if (cnt == 0) {
			for (int i = 0; i < 3; i++) {
				if (i == sel)
					continue;
				tmp = (tmp + recur(cur - 1, i, 0) + recur(cur - 1, i, 1)) % MOD;
			}
		} else
			tmp = recur(cur - 1, sel, 0);
		return dp[cur][sel][cnt] = tmp;
	}

	static int ip(String s) { // 길어
		return Integer.parseInt(s);
	}

	private static void print(Integer[][][] a) {
		StringBuilder tt = new StringBuilder();
		for (int j = 0; j < 3; j++) {
			tt.append(j + 1 + " : ");
			for (int i = 1; i < N + 1; i++) {
				String s = "";
				tt.append(s = (a[i][j][0] + "/" + a[i][j][1]).replaceAll("ull", ""))
						.append(s.length() > 2 ? " " : "\t");
			}
			tt.append("\n");
		}
		System.out.println(tt);
	}
}

• Review

최근에 계속 DP문제에 도전하고 있다. 날자와 선택을 가지고 전체 경우의 수를 직접 쓰는 작업과 점화식을 위해 누적합으로 쌓아가면서 DP를 어떻게 구성할 지 생각해봐야한다. 2차원 배열로만 구성을 하다가 1가지 더 생각을 얹어야 하게되니 시간도 배로 들어가는 느낌이다. 반드시 손으로 쓰는 작업을 게을리 하지 말자. 몸이 나쁘면 머리가 고생한다.