백준, BOJ, 9465번, 스티커: C++ [CPP]

어렵다기 보다.. 엄두를 못냈다.

사실 DP란 것을 알았으면.. N번째부터 생각해봤을텐데..

그게 안된다.

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

 

---

 

#맞은 풀이

#include<iostream>
#include<vector>
#include<algorithm>


using namespace std;

int sticker[2][100002];
int dp[2][100002]; // DP

int tc;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> tc;
    
    //테스트케이스 여러개
    while(tc--){

        //해당 테스트케이스에 대한 입력
        int length;
        cin >> length;

       //DP 초기화
        for(int i = 0; i<2; i++){
            fill(dp[i], dp[i]+length, -1);
        }
        
        for(int i = 0; i<2; i++){
            for(int j = 0; j<length; j++){
                cin >> sticker[i][j];
            }
        }
        
        //해당 테스트케이스에 대한 시행
        
        //초기값 (점화식을 돌리기 위헤)
        for(int i = 0; i<2; i++){
            dp[i][0] = sticker[i][0];
            dp[i][1] = sticker[i^1][0] + sticker[i][1];
            
        }
        
        //점화식 (하위 테이블부터 채워나감.)
        for(int i=2; i<length; i++){
            for(int j = 0; j<2; j++){
                dp[j][i] = max(dp[j^1][i-2], dp[j^1][i-1]) + sticker[j][i];
            }
        }

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

 

DP문제인지를 몰라서 생각을 못했지만

DP문제인지를 알고 나서

생각한 것

N번째의 최댓값은 어떻게 구할까???

이전의 어떤 선택까지가 과연 N번째까지 영향을 미칠까???

 

N-2번째까지 였다.

0행의 N번째 스티커의 점수는

1행의 (N-2)를 골랐거나

1행의 (N-1)을 골랐을 때 뿐이다.

?? 0행의 N-2도있잖아?? 라고 한다면

당연히 0행의 N-2를 골랐다면 1행의 N-1을 골랐을 것이기 때문에

1행의 N-1 선택지에 포함된 것이다.

 

그것만 알면 식을 세우면 된다.

항상 0행은 1행의 결과를 가져오고 1행은 0행의 결과를 가져오므로

항상 XOR연산을 통해서 다른 행의 결과를 가져오도록 했다.