[JavaScript/DP] 백준 골드 5 : 5557 - 1학년

https://www.acmicpc.net/problem/5557

5557번: 1학년

---

📌 작성한 코드 

// 5557
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

// 나오는 숫자 20 이하
// 만들 수 있는 올바른 등식의 개수
// 무조건 마지막 두 숫자 사이에 등호를 넣음

const N = Number(input.shift());
const list = input.shift().split(" ").map(Number);

const dp = Array.from({ length: N - 1 }, () => new Array(21).fill(BigInt(0)));
// dp[i][j] = i번째 숫자까지 확인했을 때, j값을 만들 수 있는 경우의 수

dp[0][list[0]] = BigInt(1);
for (let i = 1; i < N - 1; i++) {
    let cur = list[i];
    for (let j = 0; j <= 20; j++) {
        if (j + cur <= 20) dp[i][j] += dp[i - 1][j + cur];
        if (j - cur >= 0) dp[i][j] += dp[i - 1][j - cur];
    }
}

console.log(dp[N - 2][list[list.length - 1]].toString());

 

📌 설명 

dp[i][j] : i번째 숫자까지 사용했을 때, j를 만들 수 있는 경우의 수

- i는 (N-1)개, N번째 숫자는 무조건 등호로 만들어야 하는 숫자이기 때문에 dp에서 사용하지 않는다.

- j는 20까지. 만들 수 있는 수의 숫자가 0부터 20까지 이므로 배열의 크기는 21로 잡는다.

 

현재 i번째 숫자(cur)를 사용해서 j라는 숫자를 만들려고 한다.

그렇다면 j에 도달하는 방법은 i-1번째 숫자까지 계산한 결과에서 cur를 더하거나 빼는 방법 뿐이다.

즉 이전 단계에서 구한 j-cur의 개수와 j+cur의 개수를 더해주면 된다.

단, 계산한 숫자의 범위가 0~20이므로 매 계산마다 범위를 넘어가지는 않는지 확인해준다.

if (j + cur <= 20) dp[i][j] += dp[i - 1][j + cur];
if (j - cur >= 0) dp[i][j] += dp[i - 1][j - cur];

 

✅ 성공