백준 두부 모판 자르기(10937)

두부 모판 자르기

1. 순서를 강제할 수 있을까?

두부 모판을 자르는 순서는 문제의 답과 상관이 없다. 그렇기 때문에 두부 모판의 왼쪽 위부터 차례로 자르는 경우를 모두 시도해서 그 중에 최대값을 찾아보자. 두부 모판의 어떤 지점 $(i, j)$에서 가능한 선택은 다음과 같다.
1. 잘라내지 않는다.
2. $1 \times2$ 크기로 잘라낸다.
3. $2 \times1$ 크기로 잘라낸다.
잘라내는 경우는 네 방향으로 모두 가능하지만, 경우의 수가 중복되게 되므로 두부를 $(i, \ j)$ $(i, \ j \ + \ 1)$ 혹은 $(i, \ j)$ $(i \ + \ 1, \ j)$으로만 잘라내도록 정한다.

2. 이전 선택에 관련된 정보

그런데 1번 선택은 언제나 가능한 반면에 2번이나 3번선택은 경우에 따라서는 불가능할 때가 있다. 두부 모판의 범위를 벗어나거나, 이미 잘라낸 두부인 경우가 있기 때문이다.
바로 이전 행$(i - 1)$에서 $2 \times1$크기로 잘라냈다면 현재 위치$(i, \ j)$는 선택할 수 없다. 이 정보를 유지하는 것이 필요하다.

3. 시간 복잡도

아주 간단하게 생각하면 $N^2$ 넓이의 두부 모판에 대해서 매번마다 3가지 선택이 가능하므로 시간 복잡도는 $O(3^{N^2})$이 되어버린다.

우리는 여기서 $i$번째 행과 바로 이전행의 선택 여부가 저장된 $N$크기의 비트필드만 주어졌으면 언제나 답이 같음을 알 수 있다. 이처럼 참조적 투명성을 만족하기 때문에 DP함수를 작성할 수 있고, 존재하는 부분 문제의 수는 $O(N \times 2^N)$이 되고, DP함수 하나의 시간 복잡도는 $O(2^N)$이므로 최종 시간 복잡도는 $O(N \times 2^{2N})$이 된다.

4. 구현

1. getPrice(char a, char b)

F때문에 예외 처리가 귀찮아져서 함수로 따로 작성해주었다.

2. dp(int i, int b)

부분 문제들을 $[i, N)$로 나누었다. 두부 모판을 벗어난 경우 더 이상 얻을 수 있는 가격 0임이 자명하고, 메모이제이션을 적용할 cache배열은 문제의 답이 0일 수 있으므로 -1로 초기;화한다.

3. btk(int i, int j, int b, int nb)

dp함수 내에서 모든 경우를 시도하게 구현하기가 복잡해서 따로 함수로 구현해주었다. 모든 경우를 시도하고 맨 마지막에는 다음 dp함수를 호출하여서 답을 구한다.

public class Main {
	static int N; static char[][] S;
	static int[][] cache;
	
	static final int[][] price = {{100, 70, 40}, {70, 50, 30}, {40, 30, 20}};
	
	static int getPrice(char a, char b) {
		if (a == 'F' || b == 'F') return 0;
		return price[a - 'A'][b - 'A'];
	}
	
	// i번째 두부모판부터 자르기 시작할 때, 사용 가능한 두부모판이 b로 주어질 때,
	// 얻을 수 있는 최대 가격
	static int dp(int i, int b) {
		if (i == N) return 0;
		if (cache[i][b] != -1) return cache[i][b];
		return cache[i][b] = btk(i, 0, b, 0);
	}

	// i번째 두부모판을 j번째 열부터 자르는 방법을 모두 시도
	// 현재 행의 사용 가능 여부는 b, 재귀호출시 넘겨줄 다음 행의 사용 가능 여부는 nb
	static int btk(int i, int j, int b, int nb) {
		if (j == N) return dp(i + 1, nb); // i번째 열을 자르는 방법을 모두 시도한 경우 재귀 호출
		if ((b & (1 << j)) > 0) return btk(i, j + 1, b, nb); // 현재 열을 사용할 수 없는 경우
		// 선택하지 않는 경우
		int max = btk(i, j + 1, b, nb);
		// 가로로 자르는 경우
		if (j + 1 < N && (b & (1 << (j + 1))) == 0)
			max = Math.max(max, getPrice(S[i][j], S[i][j + 1]) + btk(i, j + 2, b, nb));
		// 세로로 자르는 경우
		if (i + 1 < N)
			max = Math.max(max, getPrice(S[i][j], S[i + 1][j]) + btk(i, j + 1, b, nb | (1 << j)));
		return max;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		S = new char[N][N];
		for (int i = 0; i < N; i++) S[i] = br.readLine().toCharArray();
		for (int i = 0; i < N; i++)
		cache = new int[N][1 << N];
		for (int i = 0; i < N; i++) Arrays.fill(cache[i], -1);
		System.out.println(dp(0, 0));
	}
	
}