[BOJ_C++] 9445번 : 스티커

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;

int dp[2][100001] = { 0 };
int line[2][100001] = { 0 };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t; cin >> t;
    int n;
    for (int tc = 0; tc < t; tc++) {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> line[0][i];
        for (int i = 0; i < n; i++)
            cin >> line[1][i];

        dp[0][0] = line[0][0], dp[1][0] = line[1][0];
        dp[0][1] = line[0][1] + dp[1][0], dp[1][1] = line[1][1] + dp[0][0];

        for (int i = 2; i < n; i++) {
            dp[0][i] = (dp[1][i - 1] > dp[1][i - 2]) ? line[0][i] + dp[1][i - 1] : line[0][i] + dp[1][i - 2];
            dp[1][i] = (dp[0][i - 1] > dp[0][i - 2]) ? line[1][i] + dp[0][i - 1] : line[1][i] + dp[0][i - 2];
        }

        printf("%d\n", (dp[0][n - 1] > dp[1][n - 1]) ? dp[0][n - 1] : dp[1][n - 1]);
    }

    return 0;
}

• 스티커의 합을 구하는 방법의 예시는 

• 위 방법으로 합을 구한 것 보다 아래 방법으로 구한 합이 더 크다.

• 즉, 각 스티커의 합을 구할 때 대각선의 합을 구하는 것 뿐만 아니라 대각선 뒤에 값을 구한 것과 비교하여 더 큰 값을 저장해 두어야 한다.
• 그 방법으로 계산하기 위해 dp[0][i]를 구할 땐 dp[1][i-1]과 dp[1][i-2]을 비교하여 더 큰 값을 line[0][i]와 더하여 저장해 주었다. dp[1][i]를 구할때도 같은 방법을 사용하였다.
• 마지막으로 dp[0][n-1]과 dp[1][n-1] 중 큰 값을 출력하고 프로그램을 종료하였다.

결과