[백준 9465] 스티커 (C#, C++) - soo:bak

문제 링크

9465번 - 스티커

설명

2행 n열의 스티커가 주어지는 상황에서, n (1 ≤ n ≤ 100,000)과 각 스티커의 점수가 주어질 때, 스티커를 뜯어내어 얻을 수 있는 최대 점수를 구하는 문제입니다.

스티커를 뜯으면 그 스티커의 상하좌우에 있는 스티커는 사용할 수 없습니다. 즉, 인접한 스티커는 동시에 뜯을 수 없으며, 대각선 방향의 스티커는 뜯을 수 있습니다.

접근법

열 단위로 동적 프로그래밍을 적용하여 최대 점수를 구합니다.

먼저 dp[0][c]를 c열에서 위쪽 스티커를 선택했을 때의 최대 점수로, dp[1][c]를 c열에서 아래쪽 스티커를 선택했을 때의 최대 점수로 정의합니다.

c열의 위쪽 스티커를 선택하면 c-1열에서는 아래쪽만 선택할 수 있고, c-2열에서는 아래쪽을 선택했던 것과 연결됩니다. 따라서 dp[0][c]는 현재 스티커 점수에 dp[1][c-1]과 dp[1][c-2] 중 큰 값을 더한 것입니다.

마찬가지로 dp[1][c]는 현재 스티커 점수에 dp[0][c-1]과 dp[0][c-2] 중 큰 값을 더한 것입니다.

이렇게 모든 열을 처리한 후 dp[0][n]과 dp[1][n] 중 큰 값이 답이 됩니다.

시간 복잡도는 O(n)입니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var t = int.Parse(Console.ReadLine()!);
      while (t-- > 0) {
        var n = int.Parse(Console.ReadLine()!);
        var dp = new int[2, n + 2];

        for (var r = 0; r < 2; r++) {
          var parts = Console.ReadLine()!.Split();
          for (var c = 0; c < n; c++)
            dp[r, c + 2] = int.Parse(parts[c]);
        }

        for (var c = 2; c <= n + 1; c++) {
          dp[0, c] += Math.Max(dp[1, c - 1], dp[1, c - 2]);
          dp[1, c] += Math.Max(dp[0, c - 1], dp[0, c - 2]);
        }

        Console.WriteLine(Math.Max(dp[0, n + 1], dp[1, n + 1]));
      }
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int tc; cin >> tc;
  while (tc--) {
    int n; cin >> n;
    vvi dp(2, vi(n + 2, 0));

    for (int r = 0; r < 2; r++)
      for (int c = 0; c < n; c++)
        cin >> dp[r][c + 2];

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

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

  return 0;
}