[백준] JavaScript - 카드 구매하기 (11052)

개요

문제 이름: 카드 구매하기 (11052)
문제 링크: https://www.acmicpc.net/problem/11052
플랫폼: 백준
알고리즘 분류: DP
소요 시간: 1시간

 

문제 전문

설명

입출력

 

힌트

문제 풀이

해설

이 문제는 다이나믹 프로그래밍(DP)을 사용하여 해결할 수 있는 문제입니다. 민규가 구매하려는 카드의 개수가 N개일 때, 최대로 지불할 수 있는 금액을 구하는 것이 목적입니다.

 

문제에서 주어진 조건은 다음과 같습니다.

• 카드는 카드팩 형태로만 구매할 수 있습니다.
• 카드팩은 1개부터 N개까지의 카드를 포함하고 있습니다.
• 각 카드팩의 가격이 P1부터 PN까지 순서대로 주어집니다.
• 민규는 가능한 돈을 최대한 많이 지불해서 카드 N개를 구매하려고 합니다.

이 문제를 풀기 위해서는 다음과 같은 접근 방식이 필요합니다.

1. dp[i]를 i개의 카드를 살 때 지불할 수 있는 최대 금액이라고 정의합니다.
2. 카드를 1개부터 N개까지 늘려가면서 최대 금액을 계산합니다.
3. i개의 카드를 사는 방법은 여러가지가 있습니다.
   • 1개짜리 카드팩 i개
   • 2개짜리 카드팩 (i-2)/2개 + 1개짜리 카드팩 1개
   • 3개짜리 카드팩 (i-3)/3개 + 1개짜리 카드팩 1개
   • ...(생략)
   • i개짜리 카드팩 1개
4. 위의 모든 경우를 고려하여 최대 금액을 찾습니다.
5. 최종적으로 dp[N]이 N개의 카드를 살 때 지불할 수 있는 최대 금액이 됩니다.

따라서 점화식은 다음과 같이 정의할 수 있습니다.

dp[i] = max(dp[i], dp[i-j] + P[j]) (1 <= j <= i)

여기서 P[ j ]는 j개 들어있는 카드팩의 가격입니다.

 

즉, i개의 카드를 사기 위해 j개짜리 카드팩 1개를 구매하고 (i-j)개의 카드는 이미 dp[i-j]에 계산되어 있는 최적의 방법으로 구매한다는 의미입니다.

 

모든 가능한 j에 대해 이 계산을 수행하고 최댓값을 찾으면 i개의 카드를 살 때 최대 금액을 구할 수 있습니다.

 

시도

1차 시도  (성공)

// N개의 카드를 구매할 때 지불할 수 있는 최대 금액을 구하는 문제
// 카드는 카드팩으로만 구매 가능하며, 1개부터 N개까지 들어있는 카드팩이 존재
// 민규는 가능한 많은 돈을 지불하여 카드를 구매하려고 함

// 파일 시스템 모듈을 사용하여 입력을 받아오고, 입력 데이터를 줄 단위로 분리함
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 첫 번째 줄에서 구매하려는 카드 개수 N을 가져옴
const N = parseInt(input[0]);
// 두 번째 줄에서 각 카드팩의 가격(P1부터 PN까지)을 배열로 변환
const prices = input[1].split(' ').map(Number);

// 다이나믹 프로그래밍 배열 초기화
// dp[i]: i개의 카드를 구매할 때 지불할 수 있는 최대 금액
// dp[0] = 0 (카드를 0개 구매할 때는 0원)
const dp = new Array(N + 1).fill(0);

// 작은 문제부터 차례로 해결하며 테이블 채우기
// 1개부터 N개까지의 카드를 살 때의 최대 금액을 순차적으로 계산
for (let i = 1; i <= N; i++) {
    // i개의 카드를 구매하기 위한 모든 카드팩 조합을 시도
    for (let j = 1; j <= i; j++) {
        // 현재 상태 dp[i]와 새로운 조합의 금액을 비교
        
        // dp[i-j]: (i-j)개의 카드를 구매할 때의 최대 금액
        // prices[j-1]: j개 들어있는 카드팩의 가격 (배열은 0부터 시작하므로 j-1 인덱스 사용)
        
        // i개의 카드를 구매하는 방법: j개 들어있는 카드팩을 하나 구매 + 이미 (i-j)개를 구매한 최적의 방법
        dp[i] = Math.max(dp[i], dp[i - j] + prices[j - 1]);
    }
}

// N개의 카드를 구매하는 최대 금액 출력
console.log(dp[N]);

이 코드는 다이나믹 프로그래밍(DP)을 사용하여 카드 구매 문제를 해결합니다.

1. 입력 데이터를 받아와 구매하려는 카드 개수 N과 각 카드팩의 가격을 prices 배열에 저장합니다.
2. DP 배열 dp를 N+1 크기로 초기화하고, dp[0]은 0으로 설정합니다. dp[i]는 i개의 카드를 구매할 때 지불할 수 있는 최대 금액을 나타냅니다.
3. 1개부터 N개까지의 카드를 살 때의 최대 금액을 순차적으로 계산합니다.
   • i개의 카드를 구매하기 위해 1개부터 i개까지의 카드팩을 고려합니다.
   • dp[i] = Math.max(dp[i], dp[i-j] + prices[j-1]) 점화식을 사용하여 최댓값을 갱신합니다.
   • dp[i-j]는 (i-j)개의 카드를 구매할 때의 최대 금액이고, prices[j-1]은 j개 들어있는 카드팩의 가격입니다.
4. 최종적으로 dp[N]이 N개의 카드를 구매할 때 지불할 수 있는 최대 금액이므로 이를 출력합니다.

 

사용된 주요 메서드

• fs.readFileSync(path[, options]): 동기적으로 파일의 전체 내용을 읽습니다.
• String.prototype.trim(): 문자열 양 끝의 공백을 제거한 새로운 문자열을 반환합니다.
• String.prototype.split(separator[, limit]): 문자열을 지정된 구분자를 이용하여 여러 개의 문자열로 나눕니다.
• Array.prototype.map(callback(element[, index[, array]])[, thisArg]): 배열 내의 모든 요소 각각에 대하여 주어진 함수를 호출한 결과를 모아 새로운 배열을 반환합니다.
• Array.prototype.fill(value[, start[, end]]): 배열의 시작 인덱스부터 끝 인덱스까지 지정한 값으로 채우는 메서드입니다. 채울 값과 선택적으로 시작 인덱스와 끝 인덱스를 인자로 받습니다.
• parseInt(string, radix): 문자열을 파싱하여 특정 진수의 정수를 반환합니다.
• Math.max(value1, value2, ...): 주어진 숫자 중 가장 큰 숫자를 반환합니다.

 

시간 복잡도와 공간 복잡도

• 시간 복잡도: O(N^2)
  • 1부터 N까지의 모든 카드 개수에 대해 DP 테이블을 채우는 과정에서 이중 반복문이 사용되므로 O(N^2)의 시간 복잡도를 가집니다.
• 공간 복잡도: O(N)
  
  • DP 배열이 N+1 크기를 가지므로 O(N)의 공간 복잡도를 가집니다.
  • prices 배열도 N 크기를 가지지만, 이는 입력으로 주어진 데이터이므로 추가적인 공간 복잡도로 계산하지 않습니다.