카드 구매하기

문제

언어

  • JavaScript

문제 풀이 step 1

  • dp[n] = 카드 n개를 갖기 위해 지불해야 하는 금액의 최댓값
  • k번째에 도달했을 때 1개 들어있는 카드팩을 살 수도 있고, 2개 또는 k개 들어있는 카드팩을 살 수 있습니다.
  • 카드의 개수가 k가 될 수 있는 카드팩 중에서 금액이 최대가 되는 카드팩을 구매해야 합니다.
    • k개 들어있는 카드팩 구매 + 이전까지 0개의 카드 구매
    • k-1개 들어있는 카드팩 구매 + 이전까지 1개의 카드 구매
    • …
    • 1개 들어있는 카드팩 구매 + 이전까지 k-1개의 카드 구매
  • 위의 경우 중에서 가격이 최대가 되는 경우를 구하면 됩니다.

소스 코드

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

const solution = (input) => {
	const N = parseInt(input[0]);
	const P = [0, ...input[1].split(" ").map(Number)];

	const dp = [...P];

	for (let i = 1; i <= N; i++) {
		for (let j = 1; j < i; j++) {
			dp[i] = Math.max(dp[i], dp[i - j] + P[j]);
		}
	}

	return dp[N];
};

console.log(solution(input));