[BOJ] 18427 - 함께 블록 쌓기 (Python, JavaScript)

 

 

아이디어

 

동적 계획법으로 각 블록을 사용하여 탑을 만드는 경우의 수를 구해 나간다.

 

 

풀이 #1 (Python)

 

2624번 동전 바꿔주기 문제 풀이와 유사하다.

 

0으로 채워진 H+1 크기의 리스트 dp를 생성하는데, dp[i]에는 높이 i의 탑을 만드는 경우의 수를 저장한다.

for문에서 리스트 blocks에 블록들의 높이를 입력 받고, temp에 리스트 dp를 복사하여 저장한다.

 

blocks의 블록 하나로 해당 블록의 높이만큼 탑을 쌓는 경우의 수 dp[b]를 1 증가시키고,

해당 블록을 기존 블록들을 함께 사용해 탑을 쌓아 높이 i의 탑을 경우의 수를 temp[i-b]만큼 증가시킨다.

 

높이 H의 탑을 쌓는 경우의 수를 10,007로 나눈 나머지를 출력한다.

 

import sys

input = sys.stdin.readline

def solution():
    N, M, H = map(int, input().split())
    dp = [0]*(H+1)
    for _ in range(N):
        blocks = tuple(map(int, input().split()))
        temp = dp[:]
        for b in blocks:
            dp[b] += 1
            for i in range(b+1, H+1):
                dp[i] += temp[i-b]
    print(dp[-1]%10007)

solution()

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 마찬가지 방식으로 동작한다.

 

경우의 수 최댓값이 Number 자료형의 범위를 벗어나므로 계산할 때마다 dp[i]를 10,007로 나눠 범위를 유지한다.

또 if문으로 temp[i-b]의 값이 있을 때만 dp[i]를 계산하도록 한다.

 

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

const [N, M, H] = input[0].split(' ').map(Number);
let dp = Array(H+1).fill(0);
for (let j=1; j<=N; j++) {
    const blocks = input[j].split(' ').map(Number);
    const temp = [...dp];
    for (let b of blocks) {
        dp[b] += 1;
        for (let i=b+1; i<=H; i++) {
            if (temp[i-b]) {
                dp[i] += temp[i-b];
                dp[i] %= 10007;
            }
        }
    }
}
console.log(dp[H]%10007);