[BOJ] 1106 - 호텔 (Python, JavaScript)

 

 

아이디어

 

동적 계획법으로 고객 수에 따른 최소 비용을 계산한다.

 

 

풀이 #1 (Python)

 

고객 수에 필요한 최소 비용을 저장하는 C+1 크기의 리스트 dp를 생성하고, 초기값을 비용 최댓값 100,000으로 채운다.

 

for문에서 홍보 비용과 그 고객 수를 a와 b에 입력 받고, 고객 i명을 얻는 데 필요한 최소 비용 dp[i]를 갱신해 나간다.

b의 배수 이하의 고객을 얻는 비용을 그에 맞는 a의 배수와 비교해 더 작은 값으로 갱신한다.

또 고객 수 i에서 b만큼의 고객을 홍보 비용 a로 얻었을 때의 비용인 dp[i-b]+a와 비교해 더 작은 값으로 갱신한다.

 

import sys

input = sys.stdin.readline

def solution():
    C, N = map(int, input().split())
    dp = [100000]*(C+1)
    for _ in range(N):
        a, b = map(int, input().split())
        for i in range(1, C+1):
            if a*((i-1)//b+1) < dp[i]:
                dp[i] = a*((i-1)//b+1)
            if i > b and dp[i-b]+a < dp[i]:
                dp[i] = dp[i-b]+a
    print(dp[-1])

solution()

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 마찬가지 방식으로 동작하며, 몫을 계산하기 위해 parseInt 함수를 사용한다.

 

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

const [C, N] = input[0].split(' ').map(Number);
let dp = Array(C+1).fill(100000);
for (let i=1; i<=N; i++) {
    const [a, b] = input[i].split(' ').map(Number);
    for (let j=1; j<=C; j++) {
        if (a*parseInt((j-1)/b+1) < dp[j]) dp[j] = a*parseInt((j-1)/b+1);
        if (j > b && dp[j-b]+a < dp[j]) dp[j] = dp[j-b]+a;
    }
}
console.log(dp[C]);