11726번 - 2 X n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
풀이
for문을 이용해서 Bottom-Up 방식으로 풀어보겠습니다.
N이 주어졌을 때 채우는 방법은 N-1에서 세로로 긴 1x2 타일을 하나 채우는 방법과 N-2에서 2x1타일을 2개를 채우는 방법으로 나눌 수 있습니다.
N이 1일때는 1x2 타일 1개만 가능하므로 1
N이 2일때는 1x2 타일 2개와 2x1타일 2개만 가능하므로 2
1과 2를 초기값을 바탕으로 f(N) = f(N-1) + f(N-2) 점화식을 구할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let input = require("fs").readFileSync(filePath).toString().trim();
let num = Number(input);
let answer = Array.from(new Array(num + 1), () => 0);
// 초기값
answer[1] = 1;
answer[2] = 2;
for (let i = 3; i <= num; i++) {
let sum = answer[i - 1] + answer[i - 2];
answer[i] = sum % 10007;
}
console.log(answer[num]);
11727번 - 2 X n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
풀이
앞선 문제와 유사하게 풀 수 있습니다.
for문을 이용해서 Bottom-Up 방식으로 풀어보겠습니다.
N이 주어졌을 때 채우는 방법은
- N-1에서 세로로 긴 1x2 타일을 하나 채우는 방법
- N-2에서 2x1타일을 2개를 채우는 방법
- N-2에서 2x2타일을 채우는 방법
3가지 형태로 나타낼 수 있습니다.
N이 1일때는 1x2 타일 1개만 가능하므로 1
N이 2일때는 1x2 타일 2개와 2x1타일 2개와 2x2타일 1개만 가능하므로 3
1과 3를 초기값을 바탕으로 f(N) = f(N-1) + f(N-2) * 2 점화식을 구할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let input = require("fs").readFileSync(filePath).toString().trim();
let num = Number(input);
let answer = Array.from(new Array(num + 1), () => 0);
// 초기값
answer[1] = 1;
answer[2] = 3;
for (let i = 3; i <= num; i++) {
let sum = answer[i - 1] + answer[i - 2] * 2;
answer[i] = sum % 10007;
}
console.log(answer[num]);
9095번 - 1, 2, 3 더하기
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let [_, ...input] = require("fs")
.readFileSync(filePath)
.toString()
.trim()
.split("\n")
.map(Number);
let max = Math.max(...input);
let dp = Array.from(new Array(max + 1), () => 0);
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (let i = 4; i <= max; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
let answer = input.map((x) => dp[x]);
console.log(answer.join("\n"));
11052번 - 카드 구매하기
카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오.
N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다.
즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.
풀이
Bottom UP 방식으로 answer 배열에 기록해나가며 얻을 카드 수 n개일 때의 최대값을 찾아갑니다.
얻을 카드 수 i에서 for문으로 j개를 뺀 후 Pj팩을 사는 값을 비교해 최댓값을 얻습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let [n, input] = require("fs")
.readFileSync(filePath)
.toString()
.trim()
.split("\n")
.map((x) => x.split(" ").map(Number));
let answer = new Array(n + 1).fill(0);
// i : 얻을 카드 수
for (let i = 1; i <= n; i++) {
let max = 0;
for (let j = 1; j <= i; j++) {
let sum = answer[i - j] + input[j - 1];
if (max < sum) {
max = sum;
}
}
answer[i] = max;
}
console.log(answer.pop());
16194번 - 카드 구매하기 2
카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값을 구하는 프로그램을 작성하시오.
N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다.
즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.
풀이
위 문제와 같은 방식으로 bottom up 방식의 dp로 풀어보겠습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let [n, input] = require("fs")
.readFileSync(filePath)
.toString()
.trim()
.split("\n")
.map((x) => x.split(" ").map(Number));
let answer = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
let min = Math.max(...input) * n;
for (let j = 1; j <= i; j++) {
let sum = answer[i - j] + input[j - 1];
if (min > sum) {
min = sum;
}
}
answer[i] = min;
}
console.log(answer.pop());
15990번 1, 2, 3 더하기 5
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다.
합을 나타낼 때는 수를 1개 이상 사용해야 한다.
단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
풀이
접근 방법이 어려울 수 있지만 생각보다 간단하게 풀립니다.
다른 1, 2, 3 더하기 문제에서 했듯이 n - 1, n - 2, n - 3 의 경우에서 올라오는 수를 더해주면됩니다.
단, 조건이 같은 수를 연속해서 사용할 수 없기 때문에 dp에서 저장할 값을 경우의 수를 나타내는 정수가 아닌 마지막 입력 수를 기준으로 나눈 배열로 입력합니다.
[0, 0, 0] => index + 1의 값은 마지막 숫자가 index + 1로 끝나는 경우의 수를 나타냅니다.
초기값인 1, 2, 3인 경우를 입력한후 연속해서 사용하는 index를 제외한 값을 합해서 다음 수의 입력합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let [n, ...input] = require("fs")
.readFileSync(filePath)
.toString()
.trim()
.split("\n")
.map(Number);
let max = Math.max(...input);
// 초기값으로 이중 배열을 생성합니다.
let answer = Array.from(new Array(n + 1), () => [0, 0, 0]);
// 1, 2, 3인 경우를 초기값으로 세팅합니다.
answer[1] = [1, 0, 0];
answer[2] = [0, 1, 0];
answer[3] = [1, 1, 1];
for (let i = 4; i <= max; i++) {
answer[i] = [0, 0, 0];
for (let j = 0; j < 3; j++) {
// 배열안의 값은 이전에서 연속된 수를 사용하지 않은 수입니다.
answer[i][j] =
answer[i - (j + 1)].reduce((acc, x, index) => {
return index == j ? acc : acc + x;
}, 0) % 1000000009; // 1,000,000,009 로 나누어줍니다,
}
}
input = input.map((x) => answer[x].reduce((acc, x) => acc + x, 0) % 1000000009);
console.log(input.join("\n"));