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

 

다이나믹 프로그래밍 문제입니다.

 

이웃하는 스티커를 뜯을 수 없을때 가장 높은 점수를 출력하는 문제입니다.

 

현재 찾고자 하는 위치는 

1. 한칸 전 대각선 위치

2. 두칸 전 현재 위치

두가지 방법에서 올 수 있습니다.

 

memo[0][k] = max(memo[1][k - 1], memo[1][k - 2]) + arr[0][k];

memo[1][k] = max(memo[0][k - 1], memo[0][k - 2]) + arr[1][k];

위의 사진 = max(1번, 2번) + 현재 위치 값

밑의 사진 = max(1번, 2번) + 현재 위치 값

 

#include <iostream>
#include <algorithm>
using namespace std;

int memo[2][100010];
int arr[2][100010];


void init()
{
   for (int i = 0; i < 2; ++i) {   
      for (int j = 0; j < 100010; ++j) {
         arr[i][j] = 0;
         memo[i][j] = 0;
      }
   }
}

int main(int argc, char *argv[])
{
   
   int cycle;
   cin >> cycle;
   for (int i = 0; i < cycle; ++i) {
      int n;
      cin >> n;
      init();
      for (int j = 0; j < 2; ++j) {
         for (int k = 0; k < n; ++k) {
            cin >> arr[j][k];
            memo[j][k] = arr[j][k];
         }
      }
      memo[0][1] = memo[1][0] + arr[0][1];
      memo[1][1] = memo[0][0] + arr[1][1];
      for (int k = 2; k < n; ++k) {
         for (int j = 0; j < 2; ++j) {
            if (j == 1) {
               memo[j][k] += max(memo[0][k - 1], memo[0][k - 2]);
            }
            else {
               memo[j][k] += max(memo[1][k - 1], memo[1][k - 2]);
            }
         }
      }
      int maxNum = -987654321;
      
      maxNum = max(memo[1][n - 1], memo[0][n - 1]);
      cout << maxNum << endl;
   }
   
   return 0;
}