[백준] 5557 1학년 node/javascript(자바스크립트)

(끝에 출력때문에 고생해서 블로그에 정리해두려고 한닷)

 

문제링크 : https://www.acmicpc.net/problem/5557

풀이 및 사고

모든 케이스를 깡으로 계산하면 2^100( +, -로 두 가지 경우가 계속 발생)로 시간 초과다.

근데 문제에서 0에서 20까지만 결과값을 유지한다고 주어져서 최대 100*21의 복잡도를 가지는 배열로 풀 수 있었다.

	0	1	...	20
첫 번째 값
두 번째 값
...
마지막 값

 

요런 배열을 만들어서 이전 줄을 다 순회하면서 1이상의 값(해당 경우의 수)일 때 현재 값으로 +/-한 값(인덱스)에 경우의 수를 더해주면 된다.

(문제를 대충 읽어서 주어진 출력을 다 써서 0~20 사이의 값을 만들면 되는줄 알았는데 그게 아니고 입력 제일 마지막 값이 되도록 만드는 경우의 수를 구하는 문제입니다. 저처럼 뻘짓하지 마세용)

코드

const input = require('fs').readFileSync(process.platform === "linux" ? "/dev/stdin" : "./sample.txt").toString().trim().split("\\n");

const n = Number(input[0]);
const arr = input[1].split(" ").map(Number);
const dp = [...Array(n - 1)].map(() => [...Array(21)].map(() => BigInt(0)));
let curNum, preValue, result;

dp[0][arr[0]] = BigInt(1);

for (let i = 1; i < n - 1; i++) {
  curNum = arr[i];
  for (let num = 0; num < 21; num++) {
    if (dp[i - 1][num] > 0) {
      preValue = BigInt(dp[i - 1][num]);

      result = num - curNum;
      if (result >= 0) { dp[i][result] += preValue; }
      result = num + curNum;
      if (result <= 20) { dp[i][result] += preValue; }
    }
  }
}

console.log((dp[n - 2][arr[n - 1]] === -1 ? 0 : dp[n - 2][arr[n - 1]]).toString());

느낀점

js로 푸는데 바로 틀려서 원인을 찾아봤다. 근본적인 원인은 출력값이 2^63-1 이하라는 점인데 기본 Number형은 2^53-1까지만 가능하다. 그리고 BigInt 자료형을 명시하기 위해 숫자 끝에 ‘n’이 붙게 되므로 오답처리가 된다. 그래서 toString으로 숫자만 뽑아서 출력해줬다.

 

참조 : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/BigInt