스티커

문제

언어

  • JavaScript

문제 풀이 step 1

  • dp[n][0] = 2n 개의 스티커 중에서 마지막에 위의 스티커를 뗀 경우
  • dp[n][1] = 2n 개의 스티커 중에서 마지막에 아래의 스티커를 뗀 경우
  • DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
  • 앞의 n - 1 만큼의 과정은 완성되어 있다고 가정하고, n번째를 생각해보겠습니다.
  • 마지막에 “위”의 스티커를 뗄 때 앞에 올 수 있는 경우의 수는 2가지입니다.
    • 바로 이전에 “아래”의 스티커를 뗀 경우
      • dp[n][0] = dp[n - 1][1] + top[n]
    • 바로 이전 이전에 “아래”의 스티커를 뗀 경우
      • dp[n][0] = dp[n - 2][1] + top[n]
  • 이 두 경우 중 최대값을 구하면 됩니다.
  • 마지막에 “아래”의 스티커를 뗄 때 앞에 올 수 있는 경우의 수도 마찬가지로 2가지입니다.
    • 바로 이전에 “위”의 스티커를 뗀 경우
      • dp[n][1] = dp[n - 1][0] + bot[n]
    • 바로 이전 이전에 “위”의 스티커를 뗀 경우
      • dp[n][1] = dp[n - 2][0] + bot[n]
  • 이 두 경우 중 최대값을 구하면 됩니다.
  • 최종적으로는 dp[n][0]와 dp[n][1] 중 더 큰 값이 정답이 됩니다.

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const solution = (input) => {
	let T = parseInt(input[0]);

	let res = "";
	let index = 1;
	while (T-- > 0) {
		const n = parseInt(input[index++]);
		const topArr = input[index++].split(" ").map(Number);
		const botArr = input[index++].split(" ").map(Number);

		if (n === 1) {
			res += Math.max(topArr[0], botArr[0]) + "\n";
			continue;
		}

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

		// base
		dp[0][0] = topArr[0];
		dp[0][1] = botArr[0];
		dp[1][0] = dp[0][1] + topArr[1];
		dp[1][1] = dp[0][0] + botArr[1];

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

		res += Math.max(...dp[n - 1]) + "\n";
	}

	return res;
};

console.log(solution(input));