백준 9465번 : 스티커

• Solved.ac 기준 : 실버 1
• 사용언어 C++

문제 해석 및 풀이

• 이차원 배열을 통해 입력 받음
• 뗄 수 있는 지 여부를 bool 타입 이차원 배열로 파악
• 가장 큰 스티커 떼고 주변을 false로 바꿔 준 뒤, 그 다음으로 큰거를 반복
• 더 이상 뗄 수 없으면 계산 끝
  => 해당 방식 사용시 시간 초과

---

• DP 사용
• dp[0][i] : 첫번째 행의 i번째 스티커를 뗀 경우의 최대 점수
• dp[1][i] : 두번째 행의 i번째 스티커를 뗀 경우의 최대 점수
• 다음 상태 전이를 사용
  • dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + arr[0][i]
  • dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + arr[1][i]
• max(dp[0][n-1], dp[1][n-1]) 를 출력

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool hasTrue(vector<vector<bool>>& canSticker) {
    for (int i = 0; i < 2; i++) {
        for (bool val : canSticker[i]) {
            if (val) {
                return true;
            }
        }
    }

    return false;
}

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

    int t;

    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        vector<vector<int>> arr(2, vector<int>(n));
        vector<vector<int>> dp(2, vector<int>(n));

        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < n; ++j) {
                cin >> arr[i][j];
            }
        }

        dp[0][0] = arr[0][0];
        dp[1][0] = arr[1][0];
        if (n > 1) {
            dp[0][1] = arr[0][1] + arr[1][0];
            dp[1][1] = arr[1][1] + arr[0][0];
        }

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

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