[백준/DP/C++] 9465번 스티커

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

9465번: 스티커

스티커 점수를 담는 배열 arr[i][j] 와 (i. j)를 포함하는 스티커 점수의 최대값 dp[i][j] 배열을 선언해준다
j열의 점수를 계산하면 j-1 대각선에 있는 점수랑 j-2 대각선에 있는 점수 중 큰 값을 비교해 자신의 값과 더해주면 된다

#include <bits/stdc++.h>

using namespace std;
int t, n;
int dp[2][100001], arr[2][100001];

void clearArr(int k){
    for(int i=0; i<k; i++){
        dp[0][i] = 0;
        dp[1][i] = 0;
        arr[0][i] = 0;
        arr[1][i] = 0;
    }
}

int main(void) {
    cin >> t; // 테스트케이스 개수 입력

    for(int i=0; i<t; i++){
        cin >> n; // 스티커 열 개수 입력

        for(int j=0; j<n; j++) cin >> arr[0][j];
        for(int j=0; j<n; j++) cin >> arr[1][j]; //스티커 점수 입력

        dp[0][0] = arr[0][0];
        dp[1][0] = arr[1][0];

        for(int j=1; j<n; j++){
            dp[0][j] = max(dp[1][j-1], dp[1][j-2]) + arr[0][j];
            dp[1][j] = max(dp[0][j-1], dp[0][j-2]) + arr[1][j];

        }
        cout << max(dp[0][n-1], dp[1][n-1]) << endl;
        clearArr(n); // 배열 초기화
    }

    return 0;
}

반응형