[백준] 9465번: 스티커 C++ 풀이 (DP)

DP는 정말 매번 할 때마다 새로운 느낌이라고 해야할까

접근 방식을 찾는게 가장 중요한 알고리즘이다.

본인도 실버인 문제임에도 불구하고 접근방식이 한번 꼬여서 2시간을 계속 시도 했는데,

예시는 잘되는 상황이다 보니 좀 더 할 것 같다는 생각에 계속 붙잡고 돌고 돌았던 문제였다.

 

접근:

 

본인은 접근 자체를 스티커를 선택할 수 있는 경우를 셌었다.(선택x, 첫째줄, 둘째줄)

그러나 이런 접근 보다 더 간단한 접근이 있었다.

우선 조건은 상하좌우를 스티커를 뗄 수가 없다는 점에서 감안하면,

이전 결과가 현재 결과에 영향을 준다는 점에서 DP를 사용하면 좋겠다는 생각을 했다.

일단 몇단계를 손수 해보면, 상하좌우가 막히면, 다음 단계는 대각선으로 스티커를 선택 할 수 있게되는데,

이 스티커를 선택해도 되는가는 좀 더 생각해봐야할 문제이다.

 

전략:

1단계 , 2단계, 3단계를 뛰어서 생각을 해보면

3단계 이상부터는 1, 2단계 뛰어서 조합하는게 더 많은 스티커를 뽑을 수 있다.

단순히 생각해봐도 2x2칸이 비어있다면, 한번 더 선택할 기회가 있다고 볼 수 있기 때문에

우리는 1단계, 2단계 뛰어서 가는걸 생각하기만 하면된다. 반대로 말하면

현재 상황은 1,2단계 이전의 상태를 토대로 결정 할 수 있다는 뜻이다.

1,2 단계 뛰는 순간은 선택지가 이전 선택지의 다른 선택지를 선택하는 방향으로 갈 수 밖에 없다(상하좌우 조건때문)

그래서 1행은 2행의 1,2단계 전 상태 중에 큰 거 선택, 2행은 1행의 1,2단계 전생 중의 크거 선택을 하면 최종적으로는 가장 큰 선택을 구할 수 있다.

(i번째의 값을 선택하는 수식, d는 이전 결과값, v는 스티커 값)

$ d(1,i) = max( d(2,i-1) , d(2,  i-2) ) + v[1][i]$

$ d(2,i) = max( d(1,i-1) , d(1, i-2) ) + v[2][i]$

 

구현:

#include <iostream>
using namespace std;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    int mx = 0;
    cin >> t;

    for(int i=0;i<t;i++){
        int n;
        cin >> n;

        int map[2][100001];
        int dp[2][100001];

        for(int r=0;r<2;r++)
        {
            for(int c=1;c<=n;c++){
                cin >> map[r][c];
            }
        }

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

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


        cout << max(dp[0][n] , dp[1][n]) << '\n';
        

    }
    return 0;
}