BOJ 9465 : 스티커[C++]

9465번: 스티커

 

 

DP문제

빠른 시간 내에 해결하는 것만 집중해서 푸느라 쓸데없는 계산이 있었다.

 

빨간색 칸의 최대 점수를 확인하려면 주황색, 노란색 칸의 최대 점수만 비교하면 된다.

하지만 처음 작성했던 코드는 노란색 윗 칸까지 비교하는 과정이 들어가 있었다.

 

문제를 해결하고 다른 사람들의 코드를 보는데 다들 주황색, 노란색 칸만 비교하길래,

왜 그런지 생각해봤는데 노란색 윗 칸을 비교할 필요가 없는 것이, 노란색 윗 칸을 선택하는 경우는

주황색 칸에 포함되어 있을 것이기 때문.

 

 

코드

#include <iostream>

int arr[2][100000];
int dp[2][100000];

int main() {
    int tc = 0;
    std::cin >> tc;

    for (int i = 0; i < tc; i++) {
        int n = 0;
        std::cin >> n;

        for (int j = 0; j < n; j++) {
            std::cin >> arr[0][j];
        }
        for (int j = 0; j < n; j++) {
            std::cin >> arr[1][j];
        }

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

        std::cout << std::max(dp[0][n - 1], dp[1][n - 1]) << "\n";

        for (int j = 0; j < n; j++) {
            arr[0][j] = 0;
            arr[1][j] = 0;
            dp[0][j] = 0;
            dp[1][j] = 0;
        }
    }

    return 0;
}