(9465)(DP) 백준 스티커

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

풀이

---

2행 n열로 구성되어있는 스티커이기 때문에 2차원 배열을 이용해서 dp로 구하기로 한다.

dp[i][j] 는 arr[i][j]까지의 스티커 배열 중에 스티커를 골라 최대값이 나올 수 있게 골라 더한 값을 담는다고 하자.

i)

---

arr[1][1]    arr[1][2]   arr[1][3]    arr[1][4]    arr[1][5]

arr[2][1]   arr[2][2]    arr[2][3]    arr[2][4]    arr[2][5]            ===>    dp[1][4] = dp[2][2] + arr[1][4];

vs

arr[1][1]    arr[1][2]   arr[1][3]    arr[1][4]    arr[1][5]

arr[2][1]   arr[2][2]    arr[2][3]    arr[2][4]    arr[2][5]            ===>     dp[1][4] = dp[2][3] + arr[1][4];

dp[1][4] = max(dp[2][2] + arr[1][4] , dp[2][3] + arr[1][4]);

ii)

---

arr[1][1]    arr[1][2]   arr[1][3]    arr[1][4]    arr[1][5]

arr[2][1]   arr[2][2]    arr[2][3]    arr[2][4]    arr[2][5]            ===>    dp[2][4] = dp[1][2] + arr[2][4];

vs

arr[1][1]    arr[1][2]   arr[1][3]    arr[1][4]    arr[1][5]

arr[2][1]   arr[2][2]    arr[2][3]    arr[2][4]    arr[2][5]            ===>    dp[2][4] = dp[1][3] + arr[2][4];

dp[2][4] = max(dp[1][2] + arr[2][4] , dp[1][3] + arr[2][4]); 

위와 같은 방법으로 모든 스티커에 대해 dp를 구해 나가고 마지막 배열 dp[1][N], dp[2][N] 두가지 값만 비교해서 최대값을 출력해주면 된다.

#include <stdio.h>
 
#define Max(a,b) a>b ? a:b
 
int main(){
    int T, N;
    int arr[3][100001] = { 0 };
    int dp[3][100001] = { 0 };
    
    scanf("%d", &T);
    for(int i=1; i<=T; i++){
        scanf("%d", &N);
        for(int k=1; k<=2; k++){
            for(int j=1; j<=N; j++){
                scanf("%d", &arr[k][j]);
            }
        }
        dp[1][1] = arr[1][1];
        dp[2][1] = arr[2][1];
        dp[2][2] = arr[1][1] + arr[2][2];
        dp[1][2] = arr[2][1] + arr[1][2];
        for(int j=3; j<=N; j++){
            dp[1][j] = Max(dp[2][j-1] + arr[1][j], dp[2][j-2] + arr[1][j]);
            dp[2][j] = Max(dp[1][j-2] + arr[2][j], dp[1][j-1] + arr[2][j]);
        }
        printf("%d\n", Max(dp[1][N], dp[2][N]));
        
    }
    return 0;
}