BOJ : 5557 1학년 (JS)

소스코드

let fs = require('fs');
const filePath = process.platform === `linux` ? `/dev/stdin` : `예제.txt`; 
let input = fs.readFileSync(filePath).toString().split('\n');
const c = console.log

n = Number(input[0])

let lst = input[1].split(' ').map(Number)

let dp = []

for(let i = 0 ; i < n+1 ; i++){
    dp[i] = []
    for(let j = 0 ; j < 21 ; j++){
        dp[i][j] = BigInt(0)
    }
}

for(i in lst){
    if (i == 0){
        dp[i][lst[0]] = BigInt(1)    
        continue
    }
    for (let j = 0 ; j < 21 ; j++){
        next = dp[i-1][j]
        if (next){
            if (j + lst[i] <= 20){
                dp[i][j+lst[i]] += BigInt(next)
            }
            if (j - lst[i] >= 0){
                dp[i][j-lst[i]] += BigInt(next)
            }
        }
    }
}

c(dp[n-2][[lst[n-1]]].toString())

 

풀이

맨처음에 생각한 방식은 dp[인덱스][양수,음수] 를 구분해서 더 하려고 했는데 이러면 백트래킹이랑 다를바가 뭐지? 라는 의문을 가지게 되어서 다른 방법으로 생각을 해봤습니다.

 

그래서 도출해낸 결론이 dp[연산횟수][값] 을 이용해 dp테이블을 작성했습니다. 

해당하는 연산횟수의 해당하는 값을 만들 수 있을때마다 1을 카운트 해주기로 했습니다.

 

우선 맨처음 수는 덧셈, 뺄셈 관계없이 무조건 덧셈으로 값을 가지기 때문에 무조건 1로 카운트를 해줬습니다.

그 후 0과 20 범위에 존재하는지 체크 해주고 맞다면 그 전 식에서 카운트된 수를 더해주는 방식으로 점화식을 작성했습니다. 

 

문제

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

5557번: 1학년

 

유의점

자바스크립트의 정수형의 범위는 (-(2^53 − 1)부터 2^53 − 1 이므로 BigInt를 사용해줍니다.

BigInt는 Int형이랑 연산이 되지 않고 또 숫자 뒤에 n이 붙기때문에 마지막에 출력할때 toString() 으로 문자열로 다시 변환해줍니다.