[백준 9465] 스티커

Type : 다이나믹 프로그래밍

나의 접근

1. 탐색 방법을 생각 해보았다

   50 10 100 20 40
   30 50 70  10 60

   (1) n+1 대각선

    - 상, 하, 좌, 우 스티커가 동시에 뜯기므로 제거할 수 있는 대상은 n+1칸의 대각선에 위치한 스티커이다  

   (2) n + 2 상

    - 스티커가 뜯긴 뒤 n+2 칸의 위쪽에 위치한 스티커는 온전히 제거 할 수 있다.  

   (3) n + 2 하

    - 스티커가 뜯긴 뒤 n+2 칸의 아래에 위치한 스티커는 온전히 제거 할 수 있다

2. 문제점
   (1) n+2칸 부터는 상, 하 모든 스티커를 온전히 제거할 수 있는데 모든 경우의 수를 탐색 해야 하는가?
   (2) 탐색과정에서 스티커를 뜯고 난 뒤 온전히 제거 하지 못하는 위치는 어떻게 할 것인가?
   (3) 팀색 과정에서 최대 값만 찾아 나가야 하는가?
   (4) 저장은 어떤 방식으로 해나가야 할 것인가?

3. dp[0][n] = max(dp[1][n-1], dp[1][n+1]) + cost[0][n]
   dp[1][n] = max(dp[0][n-1], dp[0][n+1]) + cost[0][n]
   점화식을 세워 계산을 해보았지만 틀린값 발생 함

모범답안 접근 및 풀이

1. 필요한 탐색
   (1) n+1, n+2 대각선

    - 온전히 뜯을 수 있는 위치의 스티커는 n+1 혹은 n+2칸의 대각선에 위치한 스티커 이다  
      ex) 50 -> 50 , 50 -> 70  

2. 불필요한 탐색
   (1) 동일한 row에 위치한 n+2칸의 스티커는 대각선을 거쳐 탐색하는 것보다 클 수 없다

   ex) (50 + 100) < (50 + 50 + 100)  

   (2) n+3 대각선에 위치한 스티커는 3보다 작은칸의 대각선을 거쳐 탐색하는 값 보다 클 수 없다

   ex) (50+10) < 50 + 50 + 100 + 10)  

3. 점화식 도출
   필수적인 탐색만 사용하여 배열의 값을 채워 나간다.

    dp[0][n] = max(dp[1][n-1], dp[1][n-2]) + cost[0][n]
    dp[1][n] = max(dp[0][n-1], dp[0][n-2]) + cost[1][n]

4. 초기화
   (1) dp 배열 탐색이 cost부터 시작되도록 초기화 한다.

    dp[0][1] = cost[0][1];
    dp[1][1] = cost[1][1];

   (2) Index Error를 방지 하고 순차적인 탐색이 가능하도록 0번째 칸을 0으로 초기화 한다.

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

주요 코드

for(int i = 2 ; i <= n ; i++){
    dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + cost[0][i];
    dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + cost[1][i];
}

깨달은 점

1. 탐색할 경우가 n에 비례하여 많아질 경우에는 필요한 탐색 경로와 의미없는 탐색 경로를 규정 해야 한다.
2. 생각한 탐색 경로를 그려놓고 어떤것이 의미 있고 어떤것이 의미 없는지 생각하면 힌트를 얻을 수 있다.
3. 0을 초기 값으로 두어 순차적인 탐색을 가능 하도록 만들 수 있다.