[BOJ] 1535 - 안녕 (Python, JavaScript)

 

 

아이디어

 

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

 

 

풀이 #1 (Python)

 

0으로 채운 (N+1)×100 크기의 2차원 리스트 dp를 생성한다.

dp[i][j]에는 i번 사람 차례에서 체력이 j일 때 얻을 수 있는 최대 기쁨을 저장한다.

 

이중 for문에서 체력이 0(인사를 한번도 하지 않은 경우)이거나 dp[i][j]에 저장된 값이 있을 때

현재 사람에게 인사한 후의 체력이 100 미만이면 인사한 후의 상태인 dp[i+1][j+L[i]]에 인사한 후의 기쁨을 저장하고,

인사하기 전과 비교해 인사하기 전의 기쁨이 더 크다면 dp[i+1][j]에 인사하기 전의 기쁨 dp[i][j]를 저장한다.

 

import sys

input = sys.stdin.readline

N = int(input())
L = tuple(map(int, input().split()))
J = tuple(map(int, input().split()))
dp = [[0]*100 for _ in range(N+1)]
for i in range(N):
    for j in range(100):
        if j == 0 or dp[i][j]:
            if j+L[i] < 100 and dp[i][j]+J[i] > dp[i+1][j+L[i]]:
                dp[i+1][j+L[i]] = dp[i][j]+J[i]
            if dp[i][j] > dp[i+1][j]:
                dp[i+1][j] = dp[i][j]
print(max(dp[-1]))

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 마찬가지 방식으로 동작하며, 최대 기쁨을 찾기 위해 Math.max를 이용한다.

 

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

const N = +input[0];
const L = input[1].split(' ').map(Number);
const J = input[2].split(' ').map(Number);
let dp = Array.from(Array(N+1), () => Array(100).fill(0));
for (let i=0; i<N; i++) {
    for (let j=0; j<100; j++) {
        if (j === 0 || dp[i][j]) {
            if (j+L[i] < 100) dp[i+1][j+L[i]] = dp[i][j]+J[i];
            if (dp[i][j] > dp[i+1][j]) dp[i+1][j] = dp[i][j];
        }
    }
}
console.log(Math.max(...dp[N]));