[백준(BOJ)] 9465번: 스티커 (Dynamic Programming, C++)

📝 문제풀이 과정

---

• DP 배열을 각 원소에서 스티커를 떼어냈을 때 가질 수 있는 최댓값이라고 하자.

• 스티커가 담긴 배열을 num이라 할 때, i번째 기준 상, 하, 좌, 우는 사용할 수 없다. 따라서 i번째 기준으로 DP[0][i]라면 DP[1][i-1], DP[1][i-2] 중에서 더 큰 값을 가져와서 현재 num[0][i]와 더한다. 그럼 num[0][i]를 떼어냈을 때까지 가장 스티커를 뗐을 때 최댓값이다.

• DP[1][i]에서는 DP[1][i-1], DP[1][i-2]에서 더 큰 값을 가져오고, 현재의 num[1][i] 값을 더해준다.
• DP[0][i], DP[1][i]에서씩 각각 구해주면, 마지막엔 DP[0][n-1], DP[1][n-1]에 담긴다. DP[0][n-1]과 DP[1][n-1]에서 더 큰 값이 스티커를 떼어냈을 때 가질 수 있는 최댓값이다.

 

 

💻 C++ 제출코드

---

#include <stdio.h>
#include <algorithm>

using namespace std;

int main(){
    int T;
    scanf("%d", &T);
    
    for(int i=0; i<T; i++){
        int n; 
        scanf("%d", &n);
        int num[2][n] = {0};
        int DP[2][n] = {0};
        
        
        for(int j=0; j<2; j++){
            for(int k=0; k<n; k++) scanf("%d", &num[j][k]);
        }
        
        DP[0][0] = num[0][0];
        DP[1][0] = num[1][0];
        DP[0][1] = num[0][1] + DP[1][0];
        DP[1][1] = num[1][1] + DP[0][0];
    
        for(int j=2; j<n; j++){
            DP[0][j] = num[0][j] + max(DP[1][j-1], DP[1][j-2]);
            DP[1][j] = num[1][j] + max(DP[0][j-1], DP[0][j-2]);
        }
        printf("%d\n", max(DP[0][n-1], DP[1][n-1]));
    }
}

 

 

👏 결과

---