자바스크립트로 알고리즘 정리하기 #11 다이나믹 프로그래밍 문제풀이 2
카드 구매하기 (boj 11052)
내 풀이
그리디 알고리즘이 먹히지 않는다는 사실을 깨닫고, 다이나믹 프로그래밍으로 접근했다. 그리디로 접근해보면, 개당 가격이 가장 비싼 카드뭉치를 사는 것이 좋다고 생각될 것이다.
이를테면 각 카드 수 별로 10, 1500, 2000 원에 판매한다고 가정해보자. 간단히 그리디 알고리즘으로만 접근하면, 개당 카드를 가장 비싸게 사는 방법은 2장씩 사는 방법이다. 장당 750원이기 때문이다.
그런데, 사야할 카드가 3장이라면, 1장과 2장을 사는 것보다는 3장을 사는 것이 좋다. 그러면 그 다음에는 보통 그러면 N장을 살때 가능한 모든 경우의 수를 비교하면 어떨까 생각이 되는데, 그렇게 생각하면 1x3, 2x1, 1x1, 3x1이렇게 모두 비교하게 된다.
이렇게 복잡하게 생각하기보다 다이나믹 프로그래밍으로 각 카드의 장수를 구매할 때 드는 최대 비용을 계속 쌓아가며 풀어보았다.
- 카드 1장을 구매하는 최대 비용은
카드 1장을 구매하는 비용외엔 경우의 수가 없다. - 카드 2장을 구매하는 최대 비용은
카드 1장을 구매하는 최대 비용+카드 1장을 구매하는 최대 비용혹은카드 2장을 한번에 구매하는 비용이다.
- 카드 3장을 구매하는 최대 비용은
카드 2장을 구매하는 최대 비용+카드 1장을 구매하는 비용혹은카드 3장을 한번에 구매하는 비용이다.
- 카드 4장을 구매하는 최대 비용은
카드 3장을 구매하는 최대 비용+카드 1장을 구매하는 비용혹은카드 2장을 구매하는 최대 비용+카드 2장을 구매하는 최대 비용혹은카드 4장을 한번에 구매하는 비용이다.
결국 부분적인 합이 최종 답안을 만든다.
그래서 이걸 코드로 표현하면
let solution = (input) => {
const n = +input[0];
let d = new Array(n + 1).fill(0);
const arr = input[1].split(' ').map((e) => +e);
arr.unshift(0);
d[0] = 0;
for (let i = 1; i < arr.length; i++) {
let max = arr[i] || 0;
for (let j = i - 1; j >= 1; j--) {
max = Math.max(max, d[j] * Math.floor(i / j) + d[i - j * Math.floor(i / j)]);
}
d[i] = max;
}
return d[n];
};
(function () {
let inputLines = require('fs').readFileSync('/dev/stdin').toString().split('\n');
console.log(solution(inputLines));
})();나는 위와 같이 표현했다.
위와 같이 표현하면 i=5인 경우에
4*1+1*13*1+2*12*2+1*11*5+0*1
위와 같은 방식으로 진행하며 최대값을 검증할 수 있다.
그런데 많은 사람들이 푼 방법은 내가 푼 방법과 달랐다.
정석 풀이
정석 풀이방법이 훨씬 쉽다.
간단히 코드로 축약해서 이야기하자면,
d[n] = max(d[n-i] + p[i]), 1<=i<=n이다.
n장의 카드를 구매하는데 드는 최대의 비용은
n-1장을 구매하는 최대 비용+1장을 구매하는 최대 비용혹은n-2장을 구매하는 최대 비용+2장을 구매하는 최대 비용혹은n-3장을 구매하는 최대 비용+3장을 구매하는 최대 비용혹은
...n-n장(0장)을 구매하는 최대 비용+n장을 구매하는 최대 비용
매 i에 이렇게 계산이 된다.
그래서 복잡도는 O(N^2)이 된다.
let solution = (input) => {
const n = +input[0];
let d = new Array(n + 1).fill(0);
const arr = input[1].split(' ').map((e) => +e);
arr.unshift(0);
d[0] = 0;
for (let i = 1; i < arr.length; i++) {
let min = arr[i];
for (let j = 1; j <= i; j++) {
min = Math.min(min, d[i - j] + arr[j]);
}
d[i] = min;
}
return d[n];
};정석풀이의 소스는 위와 같다. 위는 다만 최소값을 구하는 코드를 구현한 것이다. min만 max로 변환해주면 같다.
1, 2, 3 더하기 5 (boj 15990)
이 문제의 경우는 이전에 풀었던 1, 2, 3 더하기의 업그레이드 버전이다.
이전 1, 2, 3 더하기 문제의 경우 1, 2, 3의 숫자와 +를 이용해서 n을 만들어내면 됐는데,
이 문제의 특징은 단순히 1, 2, 3의 숫자와 +를 이용해서 n을 구성하는 것이 아니라 연속된 숫자를 만들어내면 안된다는 것에 있다.
그래서 마지막에 무엇으로 끝났는지까지 저장해준다. 마지막 숫자의 경우의 수로는 1, 2, 3을 제외하곤 없다.
그래서 [n][3] 크기의 배열을 만들면 되는데, 나는 배열을 좀 넉넉하게 쓰더라도 가독성을 높이기 위해 [0]번째는 비워줘서 [n+1][4] 크기의 배열을 만들었다.
let solution = (input) => {
input.shift(1);
input.map((e) => +e);
let n = Math.max(...input);
// let d = new Array(n + 1).fill(new Array(4).fill(0));
let d = Array.from(Array(n + 1), () => Array(4).fill(0));
let answer = '';
d[1][1] = 1;
d[1][2] = 0;
d[1][3] = 0;
d[2][1] = 0;
d[2][2] = 1;
d[2][3] = 0;
d[3][1] = 1;
d[3][2] = 1;
d[3][3] = 1;
for (let i = 4; i <= n; i++) {
for (let j = 1; j <= 3; j++) {
for (let k = 1; k <= 3; k++) {
if (i - (i - j) === k) continue;
d[i][j] += d[i - j][k] % 1000000009;
// d[4][1] += d[3][2] + d[3][3]
// d[4][2] += d[2][1] + d[2][3]
// d[4][3] += d[1][1] + d[1][2]
}
}
}
input.map((i) => (answer += d[i].reduce((acc, cur) => (acc + cur) % 1000000009, 0) + '\n'));
return answer;
};
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
rl.on('line', function (line) {
input.push(line);
}).on('close', function () {
console.log(solution(input));
process.exit();
});위에서 약간 헷갈렸던 부분은 자바스크립트에서
let d = new Array(n+1).fill(new Array(4).fill(0));위와 같은 방식으로 2차원 배열을 선언하면 안된다. n+1크기의 배열의 원소 모두가 같은 Array 레퍼런스를 가리키게 돼서 4 크기 배열의 레퍼런스가 모두 같다.
그래서
let d = Array.from(Array(n+1), () => Array(4).fill(0));위와 같은 방식으로 선언해주어야 한다.
쉬운 계단수 (boj 10844)
이 문제는 간단하게 다음으로 올 수 있는 수들이 무엇인지 생각해봄으로써 풀 수 있다.
간단하게 아래와 같이 생각해볼 수 있다.
위는 앞의 숫자가 n일 때 뒤에 올 수 있는 숫자를 적어본 것이다. 이제 이 기준으로 다음 리스트에서 끝자리가 0부터 9까지로 끝나는 수가 몇개인지 알 수 있다.
그 다음에 나올 숫자는 끝나는 숫자 기준으로 -1 +1이 나올 것이다.
이를 기준으로 소스코드를 짜면 다음과 같다.
let solution = (n) => {
let d = Array.from(new Array(101), () => new Array(10).fill(0));
let mod = 1000000000;
for (let i = 1; i < 10; i++) {
d[0][i] = 1;
}
for (let i = 1; i < n; i++) {
for (let j = 0; j < 10; j++) {
d[i][j] = ((d[i - 1][j - 1] || 0) % mod) + ((d[i - 1][j + 1] || 0) % mod);
}
}
return d[n - 1].reduce((acc, cur) => (acc + cur) % mod, 0);
};
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.on('line', function (line) {
console.log(solution(+line));
rl.close();
}).on('close', function () {
process.exit();
});이친수 (boj 2193)
이 문제도 위와 같은 사고방식을 이해했다면 금방 풀 수 있다. 가지가 어떻게 뻗어나갈 수 있는지 생각하면 된다.
일단 초기값으로 0으로 시작하는 수는 없다고 하였으니 d[0][0] = 0을 초기값으로 준다.
그리고 1로 시작하는 수는 1개 있다. 그러니 d[0][1] = 1이다.
그리고 그 다음 수부터는
0으로 끝나는 수에는 0과 1 둘 다 붙을 수 있다는 점을 인지한다.
1로 끝나는 수에는 0만 붙을 수 있다는 점을 인지한다. (연속된 1은 이친수 규칙 상 금지)
그것을 n만큼 반복하면 답이 나온다.
let solution = (n) => {
let d = Array.from(new Array(n), () => new Array(2).fill(BigInt(0)));
d[0][0] = BigInt(0);
d[0][1] = BigInt(1);
for (let i = 1; i < n; i++) {
d[i][0] = d[i - 1][0] + d[i - 1][1];
d[i][1] = d[i - 1][0];
// js int 범위 js BigInt 사용법
}
return d[n - 1].reduce((acc, cur) => acc + cur).toString();
};
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.on('line', function (line) {
console.log(solution(+line));
rl.close();
}).on('close', function () {
process.exit();
});여기서 js의 int 범위에 대해 다시한번 공부하게 되었다. 피보나치 90번째 수를 구하는데 js의 int 범위를 초과하게 된다.
그래서 BigInt를 사용하는 것이 좋다.
약 9000조까지는 자바스크립트에서 안전한 정수 범위 안에 있지만 그 수를 넘어가면 BigInt 객체를 사용하는 것이 좋다.
