본문으로 바로가기

N번재 스티커를 하나도 사용하지 않은 경우, 첫 번째 스티커를 사용한 경우, 두 번째 스티커를 사용한 경우로 나누어 문제를 해결할 수 있다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

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

int f(int, int);// 길이가 n이고 i번째 스티커를 사용한 점수의 최대값

int main() {
  scanf("%d", &t);

  while (t--) {
    memset(dp, -1, sizeof(dp));

    scanf("%d", &n);

    for (int i=1; i<=2; i++) {
      for (int j=1; j<=n; j++) {
        scanf("%d", &score[j][i]);
      }
    }

    int x = f(n, 0);
    int y = f(n, 1);
    int z = f(n, 2);

    printf("%d\n", max(x, max(y, z)));
  }

  return 0;
}

int f(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 (dp[n][i] != -1) return dp[n][i];

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

  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

댓글을 달아 주세요