동적계획법_9463_스티커

동적 계획법

 

주어진 문제를 여러 부분문제로 나누어 해결한 다음, 그 결과들로 주어진 큰 문제를 해결하는 것
F(N)을 구하기 위해서 풀어야 하는 부분 문제의 개수가 O(N)이라고 한다면, 이 답을 모두 저장할 메모리의 크기로 O(N)이 필요하며, 각각의 문제를 푸는 시간은 O(1)로, 전체 소요시간은 O(N)이다.

분할 정복 VS DP
위 두개 알고리즘의 가장 큰 차이점은 분할정복은 문제를 분할 했을 때, 겹치는 문제가 없다는 것이다. 하지만 DP는 겹치는 문제가 발생하기 때문에 필요 이상의 호출로 인한 시간 및 메모리 낭비 방지를 위해 메모이제이션을 한다.

Greedy VS DP
모든 경우를 메모리가지 소비해가며 샅샅이 체크하는 점에서 실행시간이 그리디보다는 길지만, 더 폭 넓은 범위에서 경우의수를 따지기 때문에 근사치가 아닌 정확한 값을 얻을 수 있다.

TopDown(재귀) VS BottomUp(반복)
전자는 가독성이 좋고, 문제 해결에 필요한 점화식을 이해하기 쉽다.
후자는 코드가 길고, 가독성이 떨어지지만, 시간과 메모리를 전자에 비해 소량 더 절약할 수 있다.

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

9465번: 스티커

 

어제 풀었던 1로 만들기보다는 조금 더 어려운 난이도이다. DP의 배열이 1차원이 아닌 2차원 배열을 사용하기 때문에 조건 또한 조금 더 까다롭다. 
항상 키포인트는 문제를 읽고 이 문제를 풀기 위해 문제를 쪼개면서 반복적으로 작용하는 부분문제를 찾아서 점화식을 작성하는 것이다. 

문제를 처음 읽었을 때는 재귀함수를 사용한 DFS로도 풀리지 않을까하는 생각이 들었지만, 시간초과가 날 것 같기도 하고 일단은 DP를 연습하는 기간이니 점화식을 구성하는 연습을 해보자 .

먼저, 고려해야 할 사항은 뗀 스티커 주변에 있는 스티커는 사용할 수 없다는 점이다. 
이 말을 조금 돌려서 생각해보면 첫 번째 열부터 스티커를 뗄 필요가 없다는 것이다. 필자도 그렇고,,,, 단순한 사람의 심리상 가장 앞에서부터 시작하는 것이 심리적으로 안정되지만, 최대의 가치를 구해야 하는 마당에 0열에 10, 20점이 있고, 1열에 100, 200이 있다면 당근 1열부터 스티커를 뗄 것이다. 극단적인 예로 비교하긴 했지만, 이 또한 확실히 보장할 수 없기 때문에 우리는 이전 문제와 마찬가지로 모든 경우의 수를 살펴봐야 한다. 

하지만 매번 그랬듯 모든 경우의 수는 우리가 아니라 컴퓨터가 해줄 것이니 우리는 점화식을 생각해서 컴퓨터에게 넘겨주자. 다시 원초적인 생각으로 돌아와서 여기서 중요한 것은 몇번 열부터 스티커를 뜯을 것인지, 특정 열에서 스티커를 뜯었다면 그 주변에 있는 열의 상태(뜯어져 있나? 아님 안 뜯어져 있나?)를 기록해주면서 점화식을 짜야 한다는 것이다.

그렇다면 두가지의 파라미터를 사용하여 함수를 구성해보자. 

/**
*	@param
*	k 	: 스티커를 떼기 시작할 열
*	letf	: 스티커를 뗀 왼쪽 열의 상태
*		- 0 : 아무것도 안 뗌
*		- 1 : 위쪽을 뗌
*		- 2 : 아래쪽을 뗌
**/
detach(k, left)

예를 들면서, 점화식을 일반화 해보자. 가장 처음부터 스티커를 떼기 시작한다면 함수의 시작은 detach(0,0)이 될 것이다. 0번 열부터 스티커를 떼기 시작하고, 시작 열이기 때문에 왼쪽 열은 존재하지 않기 때문이다. 
1. 0번 열에서 위쪽 스티커를 떼는 경우 -> 0번 열 위쪽스티커 가치 + detach(1,1)
2. 0번 열에서 아래 스티커를 떼는 경우 -> 0번 열 아래 스티커 가치 + detach(1,2)
3. 아무런 스티커를 떼지 않고 넘어가는 경우 -> detach(1,0)

위의 3가의 경우의 수를 함수화 해보자. 

detach(0, 0) = Max( {0번 열 위쪽스티커 가치 + detach(1,1)},  { 0번 열 아래 스티커 가치 + detach(1,2) }, { detach(1,0) } )

위의 함수를 일반화 하면 아래와 같을 것이다. 

k열에서만 스티커를 떼는 최대 가치 
detach(k, left) = Max( 
						왼쪽 열 0행 가치 + detach( k+1, 1 ),
                        왼쪽 열 1행 가치 + detach( k+1, 2 ),
                        detach( k+1, 0 )
                      )

 

그렇다면 이제 위의 점화식을 기반으로 해서 코딩을 해보자. 먼저 탑 다운 방식이다.
메모이제이션에 사용되는 DP배열을 점화식에 맞게 크기를 설정해주고, N행 3(상태)열, 아무것도 안 뜯은 경우, 아래를 뜯은 경우, 위를 뜯은 경우 세 가지 경우의 수를 비교해 최댓값을 구한다.

아무것도 안 뜯은 경우 : 세 가지 경우의 수를 모두 비교 
위쪽을 뜯은 경우 : 아무것도 안 뜯은 경우와 (아래쪽을 뜯은 경우 + 다음 열로 이동)의 최댓값을 구한다.
아래를 뜯은 경우 : 아무것도 안 뜯은 경우와 (위    쪽을 뜯은 경우 + 다음 열로 이동)의 최댓값을 구한다.

package DynamicProgamming;

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

public class _9463_스티커 {
	
	static int N;
	static int [][]sticker;
	static int [][]DP;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		//테스트 케이스만큼 반복
		while(T --> 0) {
			
			//열의 개수
			N = Integer.parseInt(br.readLine());
			sticker = new int[2][N];
			
			//스티커 점수 초기화
			for(int i=0; i<2; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					sticker[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			DP = new int[N][3];
			//-1로 세팅
			for(int []i : DP) Arrays.fill(i, -1);
			
			
			
			int max = detachingSticker(0, 0);
			sb.append(max).append("\n");
		}
		System.out.println(sb.toString());
	}

	private static int detachingSticker(int k, int left) {
		// TODO Auto-generated method stub
		if(k==N) return 0;
		if(DP[k][left] != -1) return DP[k][left];
		
		int sum = detachingSticker(k+1, 0);
		if(left != 1) sum = Math.max(sum, sticker[0][k] + detachingSticker(k+1, 1));
		if(left != 2) sum = Math.max(sum ,sticker[1][k] + detachingSticker(k+1, 2));
		
		DP[k][left] = sum;
		
		return sum;
	}
}

 

반대로 바텀업은 아래에서 부터 쌓아올리기 때문에 위와는 약간의 다른 사고방식을 가져야 한다. 탑다운 방식은 특정 열을 기준으로 왼쪽 열의 상태에 따라 경우의 수를 나누었다면, 이번에는 가장 밑에서부터 기준을 잡고 시작한다. 가치는 0이상 100이하의 정수이므로 스티커의 최솟값이 0이다. 즉 가치합의 최솟값이 0이라고 생각할 수 있다. 
탑 다운과는 반대로 상태에 따라 시작부분을 정한 상태로 쌓아올라가기 때문에 꼭대기에 이른 값들 중 최댓값을 구해야 한다.

package DynamicProgamming;

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

public class _9463_스티커_바텀업 {
	
	static int N;
	static int [][]sticker;
	static int [][]DP;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		//테스트 케이스만큼 반복
		while(T --> 0) {
			
			//열의 개수
			N = Integer.parseInt(br.readLine());
			sticker = new int[2][N];
			
			//스티커 점수 초기화
			for(int i=0; i<2; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					sticker[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			DP = new int[N+1][3];
			for(int i=0; i<N; i++) {
				DP[i+1][0] = Math.max(DP[i+1][0], Math.max(DP[i][0], Math.max(DP[i][1], DP[i][2])));
				DP[i+1][1] = Math.max(DP[i+1][1], Math.max(DP[i][0], DP[i][2]) + sticker[1][i]);
				DP[i+1][2] = Math.max(DP[i+1][2], Math.max(DP[i][0], DP[i][1]) + sticker[0][i]);
			}
			
			int max = Math.max(DP[N][0], Math.max(DP[N][1], DP[N][2]));
			sb.append(max).append("\n");
		}
		System.out.println(sb.toString());
	}

}

 

아직은 미숙해서 그런지 시작부터 바텀업으로 풀라고 하면 절대 못풀것 같다... 각 방법의 결과는 크게 차이 나지 않지만, 위의 정리와 마찬가지로 바텀업 방식이 코드는 더 길고 가독성은 떨어지지만, 메모리와 시간적인 면에서 소량 절약할 수 있는 것을 확인할 수 있다.