[BOJ 9465] 스티커

문제

스티커

https://www.acmicpc.net/problem/9465

 

 

풀이

설명

있는 스티커 점수 합의 최댓값을 구하는 문제입니다.

 

DP를 이용해 해결할 수 있습니다.

 

dp[i][j]는 (i, j)번째 스티커를 골랐을 때 얻을 수 있는 점수 합의 최댓값입니다.

 

스티커의 점수를 저장한 n * 2 크기의 배열을 stickers라고 할 때,

점화식은 다음과 같습니다.

dp[i][j]는 다음 두 값중 더 큰 값에  stickers[i][j]를 더한 값입니다.

• dp[i - 1][1 - j]
• dp[i - 2][1 - j]

 

예시 코드

function solution() {
  const T = Number(input());
  const answer = [];
  for (let tc = 0; tc < T; tc++) {
    const n = Number(input());
    const stickers = Array.from({ length: 2 }, () =>
      input().split(" ").map(Number)
    );

    const arranged = [];
    for (let i = 0; i < n; i++) {
      arranged.push([stickers[0][i], stickers[1][i]]);
    }

    const dp = Array.from({ length: n + 1 }, () => [0, 0]);

    dp[1][0] = arranged[0][0];
    dp[1][1] = arranged[0][1];

    for (let i = 2; i <= n; i++) {
      for (let j = 0; j <= 1; j++) {
        dp[i][j] =
          Math.max(dp[i - 1][1 - j], dp[i - 2][1 - j]) + arranged[i - 1][j];
      }
    }

    answer.push(Math.max(dp[n][0], dp[n][1]));
  }

  return answer.join("\n");
}