백준 9465 스티커

dp로 푸는 문제.

 

알게된 점

점화식을 세울 때 arr[r][c]를 포함하는 경우와 포함하지 않는 경우만 생각하지 말자

이번 문제는 arr[r][c]를 뽑을 수 있는 이전 위치를 고려해야 했다!

---

dp는 최적해의 부분최적해를 생각하며 점화식을 세워야 한다.

 

처음 접근방식

arr[r][c] 의 스티커를 떼는 경우와 떼지 않는 경우를 고려해서 점화식을 세우려고 했다.

 

올바른 접근방식

arr[r][c]의 스티커를 뗄 수 있는 경우만 고려하고, arr[r][c] 스티커를 뗄 수 있는 이전 위치 (arr[1][c-1] or arr[1][c-2] 혹은 arr[0][c-1] or arr[0][c-2]) 를 부분최적해로 보는 것 이었다.

 

---

 

점화식

r=0인 경우

dp[r][c] = max{dp[1][c-1], dp[1][c-2]} + arr[r][c]

 

r=1인 경우

dp[r][c] = max{dp[0][c-1], dp[0][c-2]} + arr[r][c]

---

 

의문이 들었던 점

r=0 인 경우를 예로 들면

dp[1][c-1], dp[1][c-2], dp[0][c-2] 와 같이 dp[0][c-2] 부분도 고려해야 할 것 같았다. 

 

하지만

dp[r][c] 를 계산하는데 dp[0][c-2]는 필요하지 않았다.

 

이유는

dp[1][c-1]에 이미 dp[0][c-2]를 고려한 값이 계산되어 있기 때문이다.

 

쉽게 말하자면

dp[0][c-2] 다음 열의 대각선 부분까지 떼어낸 것이 항상 더 이득이다. 그리고 그 경우는 dp[1][c-1]에 들어있을 것이기 때문.

 

---

 

코드

import java.util.*;
import java.io.*;

public class Main {

    static int N;
    static int[][] arr;
    static int[][] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int T = Integer.parseInt(br.readLine());

        for(int t=0;t<T;t++){
            N = Integer.parseInt(br.readLine());
            arr = new int[2][N];
            dp = new int[2][N];
            for(int r=0;r<2;r++){
                st = new StringTokenizer(br.readLine());
                for(int c=0;c<N;c++){
                    arr[r][c] = Integer.parseInt(st.nextToken());
                }
            }

            dp[0][0] = arr[0][0];
            dp[1][0] = arr[1][0];

            for(int c=1;c<N;c++){
                for(int r=0;r<2;r++){
                    if(r==0){
                        dp[r][c] = Math.max(c-1>=0?dp[1][c-1]:0,c-2>=0?dp[1][c-2]:0) + arr[r][c];
                    }else if(r==1){
                        dp[r][c] = Math.max(c-1>=0?dp[0][c-1]:0,c-2>=0?dp[0][c-2]:0) + arr[r][c];
                    }
                }
            }
            System.out.println(Math.max(dp[0][N-1],dp[1][N-1]));
        }

    }

}