백준 9465번, 스티커(C, C++)

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

9465번: 스티커

int main(){
    int dp[2][20001];
    int s[2][200001];
    int T;
    int n;

    cin>>T;
    while(T--){
        cin>>n;

    for(int i = 0; i < 2; i++){
        for(int j = 0; j < n; j++){
        cin >> s[i][j];
        }
    }

    
    dp[0][0] = s[0][0];
    dp[1][0] = s[1][0];
    dp[0][1] = s[0][1] + dp[1][0];
    dp[1][1] = s[1][1] + dp[0][0];

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

    cout<<max(dp[0][n-1], dp[1][n-1])<<endl;
    }
return 0;
}

 

위 사진에서 1칸씩 대각선으로 가는 방법과 2칸을 건너뛰는 대각선으로 가는 방법이 있습니다.

이것으로 점화식을 세울 수 있습니다.

dp[0][i] = s[0][i] + max(dp[1][i-1], dp[1][i-2])

 

.

이 그림의 점화식은 dp[1][i] = s[1][i] + max(dp[0][i-1], dp[0][i-2])로 세울 수 있습니다

첫 번째 그림의 점화식으로 나타나지는 값과 두 번째 그림의 점화식으로 나타나는 값의 최소를 출력을 합니다.

 

사실 이 문제는 BFS로 해결하려고 하였지만, N의 최대값이 10만으로 주어져 BFS를 사용하게 되면

시간초과가 날 것으로 생각해 해결 방법을 DP로 바꿨습니다.