[BOJ] 1415 - 사탕 (Python, JavaScript)

 

 

아이디어

 

DP로 사탕 가격의 합에 대한 경우의 수를 구해 나가고, 에라토스테네스의 체로 가격 합이 소수인지 확인한다.

 

 

풀이 #1 (Python)

 

dp[i]는 가격 합이 i인 사탕을 사는 방법의 수를 나타낸다.

 

import sys

input = sys.stdin.readline

def solution():
    N = int(input())
    candies = dict()
    total = 0
    zero = 1
    for _ in range(N):
        price = int(input())
        if price:
            candies[price] = candies.get(price, 0)+1
            total += price
        else:
            zero += 1
    P = [1]*(total+2)
    P[0] = P[1] = 0
    for i in range(2, int(total**0.5)+1):
        if P[i]:
            for j in range(i*2, total+1, i):
                P[j] = 0
    dp = [0]*(total+1)
    dp[0] = 1
    M = 0
    for price, cnt in candies.items():
        for i in range(M, -1, -1):
            for j in range(1, cnt+1):
                _price = i+price*j
                if _price > total:
                    break
                if _price > M:
                    M = _price
                dp[_price] += dp[i]
    res = 0
    for i in range(total+1):
        if P[i]:
            res += dp[i]
    print(res*zero)

solution()

 

 

 

풀이 #2 (JavaScript)

 

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

function solution() {
    const N = Number(input[0]);
    let candies = new Map();
    let total = 0;
    let zero = 1;
    for (let i=1; i<=N; i++) {
        const price = Number(input[i]);
        if (price) {
            if (candies.has(price)) candies.set(price, candies.get(price)+1);
            else candies.set(price, 1);
            total += price;
        }
        else zero += 1;
    }
    let P = Array(total+2).fill(1);
    P[0] = P[1] = 0;
    for (let i=2; i<=parseInt(Math.sqrt(total)); i++) {
        if (P[i]) {
            for (let j=i*2; j<=total; j+=i) P[j] = 0;
        }
    }
    let dp = Array(total+1).fill(0);
    dp[0] = 1;
    M = 0;
    for (const [price, cnt] of candies) {
        for (let i=M; i>=0; i--) {
            for (let j=1; j<=cnt; j++) {
                const _price = i+price*j;
                if (_price > total) break;
                if (_price > M) M = _price;
                dp[_price] += dp[i];
            }
        }
    }
    let res = 0;
    for (let i=2; i<=total; i++) {
        if (P[i]) res += dp[i];
    }
    console.log(res*zero)
}

solution();