문제 링크
정말 오랜만에 풀이하는 알고리즘,, 코테 준비를 위해 중간 중간 풀었는데 한동안 뜸했더니 실력이 처참해졌다..😱
왜 올리는데는 한 세월이고 떨어지는데는 한 순간인가..
사족은 넘기고 문제로 가면 평이한 Dp 문제이다.
아직까지는 나 Dp에요~ 하는 문제는 금방 점화식 세우고 풀 수 있는거 같다.
문제 풀이 빌드업
-
dp배열의 index와 value를 뭐로 할까
등수의 수가 계속 update되고 구해야하는 해이므로 value로 할까.
처음에는 +와 -로 두개를 나눠야하나 싶었는데 이전 분기에서 +인지 -인지는 중요하지않고 수식을 통해 나온 수가 중요했기 때문에 index 또한 몇번째 수를 포함한 수식인지로 정했다. -
top-down 일까 bottom-up일까
잘 설명은 안되지만 dp[0]이랄까 초기값이 있기도 하고 bottom-up으로 해야할 것 같은 느낌이 든다. -
그래서 구해야하는 값은 무엇인가
dp[등호 이전까지의 idx][원하는 값 == 등호 이후의 수 == 마지막 수] = 가능한 수식
으로 글로 나타낼 수 있겠다.
시행착오
- 문제에서 올바른 등식의 개수는 263-1 이하이다. 라고 나와있다ㅎㅎ
보긴했었는데 javascipt 니까 괜찮겠지 라는 안일한 생각과 number형의 크기가 int보단 크다고 대충 알고 있어 정답까지 시간이 더 걸리게됐다.
이 기회에 공부한 자스 Number~
_Number 는 원시 래퍼 객체입니다.
Number 생성자는 숫자를 다루기 위해 상수와 메소드를 가지고 있습니다. 다른 타입의 값은 Number() 함수를 사용하여 숫자로 바꿀 수 있습니다.
일반적인 숫자는 '배정밀도 부동소수점 숫자(double precision floating point number)'로 알려진 64비트 형식의 IEEE-754에 저장됩니다.
임의의 길이를 가진 정수는 BigInt 숫자로 나타낼 수 있습니다. 일반적인 숫자는 253이상이거나 -253이하일 수 없다는 제약 때문에 BigInt라는 새로운 자료형이 만들어졌습니다._
BigInt
BigInt는 정수 리터럴의 뒤에 n을 붙이거나(10n) 함수 BigInt()를 호출해 생성할 수 있습니다.
BigInt와 Number는 어떤 면에서 비슷하지만 중요한 차이점이 있습니다. 예컨대 BigInt는 내장 Math 객체의 메서드와 함께 사용할 수 없고, 연산에서 Number와 혼합해 사용할 수 없습니다. 따라서 먼저 같은 자료형으로 변환해야 합니다. 그러나, BigInt가 Number로 바뀌면 정확성을 잃을 수 있으니 주의해야 합니다.
라고 한다.
- 두번째 실수는 BigInt는 그냥 콘솔 찍으면 뒤에 n이 붙는다는 것이다.
따라서 정답을 print 할때 값을 toString해야한다.
정답 풀이
const fs = require("fs");
let [n, ...arr] =fs.readFileSync("/dev/stdin")
.toString()
.trim()
.split(/\s/)
.map(Number)
let MAX_VALUE =20
let dp=Array.from({length:n-1},e=>Array.from({length:MAX_VALUE+1},e=>BigInt(0)));
dp[0][arr[0]]=BigInt(1)
for(let i=1;i<n-1;i++){
for(let j=0;j<=20;j++){
if(dp[i-1][j]===0)continue;
if(j+arr[i]<=20){//+
dp[i][j+arr[i]]+=dp[i-1][j]
}
if(j-arr[i]>=0){ // -
dp[i][j-arr[i]]+=dp[i-1][j]
}
}
}
console.log(dp[n-2][arr[n-1]].toString())
