[25.03.09] 스티커 (DP)
DP 의 핵심은 점화식 + 메모이제이션
1) 문제를 작은 부분(과거의 부분)으로 나눠서 현재의 상황에 대한 점화식 작성
2) 과거의 결과들을 DP 테이블(메모이제이션 배열) 을 통해 시간 복잡도 감소
로 정리할 수 있다.
3) 이런 계산 과정에서 가장 첫번째의 DP 수행일때는 과거의 것들이 없기에 초기화하고 DP를 수행하는 것이 필수
그 중 Top-Down , Bottom-Up
Top-Down에 대한 나의 오답: 작은 부분==과거의 부분으로부터 현재의 답을 유도해야된다. 문제에서 대놓고 점화식 형태로 나타내어있거나 바꾸기 힘들때는 우선 시간의 흐름이 증가하는 방향은 어떤 방향인가를 봐야한다.
이러한 예시를 자세히 들여다보면 각 스티커 점수는 음수가 없다. 즉 왼쪽에서 오른쪽으로 스티커를 뗀다고 가정하면 오른쪽으로 갈수록 점수가 무조건 증가한다 == 과거의 부분은 왼쪽이 되는거고 오른쪽 부분은 왼쪽의 메모이제이션으로부터 구하면 되는 것이다.
따라서 최댓값을 구할때는 맨 오른쪽에 있는 열까지 DP를 수행하면 된다는 것이다.
점화식:
20을 현재 떼는 스티커로 가정해보자.
이럴때 20을 땔려면 과거의 상황에서 100이나 10 스티커를 떼버리면 안된다.
20까지 왔을때의 최댓값은 전 과정에서의 최댓값 + 현재 스티커 값(20) 이므로 어떤 과정까지 와야 20 스티커를 뗄 수 있는지 모든 경우를 따져봐야한다.
우선 그 전 열에서는 100 제외 모든 스티커가 가능하고, 같은 열에서는 10은 어차피 안되니까 같은 열에서는 고민할 필요가 없다.
그러면 이제 기준 잡은 20으로부터 몇개의 전 열까지 이 20에 영향을 미칠 것인가를 찾아봐야하는데... (==점화식 세우기)
20을 i번째 열이라고 한다면 , 1열 ~ i-2열에서는 모든 스티커가 i번째 윗 스티커(20) 에 다이렉트로 영향을 줄 것인가?
1) 70 부분
20까지 왔을때의 최댓값은 70 스티커 부분에서 비롯된다. 70의 최댓값을 구하는 과정에서 많은 스티커를 떼는 경로가 있을 것이다. 근데 점화식에서는 그건 내 알빠가 아니고 알아서 지지고 볶은 상태의 최댓값이 나온 70에서 20이 비롯된다. 메모이제이션이 이것을 이용하는 것이다.
2) 50 부분
마찬가지로 50까지 왔을때의 최댓값이 20의 최댓값을 결정한다.
당연하게 50의 최댓값이 어떻게, 어떤 스티커를 떼는 경로로 최댓값이 나왔냐는 중요하지 않다. 이미 메모이제이션 50 부분에 이 최댓값이 모든 경로를 통해 비교 후 최댓값을 저장해놓았기 때문이다.
3) 10 부분
10 부분을 보면 얘도 50때와 마찬가지로 10이 있는 열과 20이 있는 열 사이의 하나의 열을 건너뛰고 선택한다면 10 스티커로 인해서 20 스티커 최댓값을 구할때 고려해야하는 것 아닌가? 생각할 수도 있지만, 10으로 인한 스티커 값은 70의 최댓값을 메모이제이션 할때 반영이 되어있다. 즉 중복된다. 따라서 10은 해당되지 않는다.
4) 나머지
첫번째 열의 50일때도 마찬가지로 2번째 열의 50 , 3번째 열의 70 에서의 메모이제이션에서 반영되어 있다.
30도 마찬가지...
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
//DP , TopDown
static int T;
static int[][] dp;
static int[][] sticker;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
for(int i=0; i<T; i++){
int n = Integer.parseInt(br.readLine());
sticker = new int[2][n+2];
dp= new int[2][n+2];
// dp[0][0]=0;
// dp[1][0]=0;
// dp[0][1]=0;
// dp[1][1]=0;
for(int j=0; j<2; j++){
String[] s;
s= br.readLine().split(" ");
for(int z=2; z<n+2; z++){
sticker[j][z] = Integer.parseInt(s[z-2]);
}
}
for(int j=2; j<n+2; j++){
dp[0][j] = Math.max(dp[1][j-1] , dp[1][j-2]) + sticker[0][j];
dp[1][j] = Math.max(dp[0][j-1] , dp[0][j-2]) + sticker[1][j];
}
System.out.printf("%d\n",Math.max(dp[0][n+1],dp[1][n+1]));
// [0][i] >관련> [1][i-1] or [1][i-2]
// [1][i] >관련> [0][i-1] or [0][i-2]
}
}
}
내 행동 오답:
Top-Down이면 자꾸 미래를 보지 말고 과거를 봐라. Top-Down인데 미래의 답을 가지고 현재의 답을 구하려하니까 틀리는거다.
==
난 자꾸 스티커 50을 떼버리면 나머지 녹색 부분에서만 이제 스티커를 뗄 수 있으니 여기서 DP를 어떻게 쓰지? 하고 있었다. 스티커 50을 떼는게 현재라면 , 그 이후 녹색은 미래이다. 우리가 원하는건 Top-Down일때는 현재를 과거의 문제를 통해서 찾아야하는데 뻘짓 하지 말자.
과거를 이용하여 점화식을 구할때는 해당 각각의 항에서 어디까지 커버되고 있는지 확인하라.
== 결론적으로 점화식은
// [0][i] >관련> [1][i-1] or [1][i-2]
// [1][i] >관련> [0][i-1] or [0][i-2]
이다. 이때 각각의 항인 [1][i-1] 와 [1][i-2] , 또는 [0][i-1] 와 [0][i-2] 가 어디까지 반영해서 들어가고 있는지를 잘 좀 보자.
예를 들면 위의 설명 3번의 10부분에서 10도 얼핏보면 현재 스티커 최대점수에 영향을 미칠것 같지만 이미 10부분은 70 스티커 최댓값을 찾을때 반영되어 흡수된다.
