본문으로 바로가기
  • DP로 문제를 해결할 수 있다.
  • 임의의 열에 대하여 스티커를 사용하지 않은 경우, 첫 번째 스티커를 사용한 경우, 두 번째 스티커를 사용한 경우로 나누어 문제를 해결한다.
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int t, n;
int cache[100001][3];
int score[100001][3];

int dp(int n, int i) {
  if (n == 1) {
    if (i == 0) return 0;
    if (i == 1) return score[1][1];
    if (i == 2) return score[1][2];
  }
  if (cache[n][i] != -1) return cache[n][i];
  // 스티커를 사용하지 않는 경우
  if (i == 0) {
    int x = dp(n-1, 0);
    int y = dp(n-1, 1);
    int z = dp(n-1, 2);
    return cache[n][i] = max(x, max(y, z));
  }
  // 첫 번째 스티커를 사용하는 경우
  else if (i == 1) {
    int x = dp(n-1, 0) + score[n][1];
    int y = dp(n-1, 2) + score[n][1];
    return cache[n][i] = max(x, y);
  }
  // 두 번째 스티커를 사용하는 경우
  else if (i == 2) {
    int x = dp(n-1, 0) + score[n][2];
    int y = dp(n-1, 1) + score[n][2];
    return cache[n][i] = max(x, y);
  }
  return 0;
}

int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (int i=1; i<=2; i++) {
      for (int j=1; j<=n; j++) {
        scanf("%d", &score[j][i]);
      }
    }
    memset(cache, -1, sizeof(cache));
    printf("%d\n", max(dp(n, 0), max(dp(n, 1), dp(n, 2))));
  }
  return 0;
}

'Programming > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 11053: 가장 긴 증가하는 부분 수열  (0) 2018.05.23
[BOJ] 2156: 포도주 시식  (0) 2018.05.15
[BOJ] 9465: 스티커  (0) 2018.05.15
[BOJ] 2193: 이친수  (0) 2018.05.15
[BOJ] 11057: 오르막 수  (0) 2018.05.15
[BOJ] 10844: 쉬운 계단 수  (0) 2018.05.15

댓글을 달아 주세요