2225번 - 합분해
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
풀이
2차원배열을 생각 못해서 점화식을 찾는데 오래 걸렸습니다.
N, K를 2차원 배열로 생각하고 dp로 풀면 쉽게 풀리는 문제입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let [N, K] = require("fs")
.readFileSync(filePath)
.toString()
.trim()
.split(" ")
.map(Number);
let dp = Array.from(new Array(K), () => new Array(N + 1).fill(0));
dp[0] = new Array(N + 1).fill(1);
for (let i = 1; i < K; i++) {
for (let j = 0; j <= N; j++) {
for (let h = 0; h <= j; h++) {
dp[i][j] += dp[i - 1][h] % 1000000000;
}
}
}
console.log(dp[K - 1][N] % 1000000000);
1149번 - RGB 거리
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다.
각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
풀이
dp 문제로
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let [N, ...input] = require("fs")
.readFileSync(filePath)
.toString()
.trim()
.split("\n");
input = input.map((x) => x.trim().split(" ").map(Number));
let dp = Array.from(new Array(Number(N)), () => new Array(3).fill(0));
dp[0] = input[0];
for (let i = 1; i < N; i++) {
dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + input[i][0];
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + input[i][1];
dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + input[i][2];
}
console.log(Math.min(...dp.pop()));
1309번 - 동물원
어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.
이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다.
이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.
동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자.
사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let N = require("fs").readFileSync(filePath).toString().trim();
N = Number(N);
let dp = [1, 3];
for (let i = 2; i <= N; i++) {
dp[i] = (dp[i - 1] * 2 + dp[i - 2]) % 9901;
}
console.log(dp.pop());
11057번 - 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.
예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.
수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let N = require("fs").readFileSync(filePath).toString().trim();
N = Number(N);
let dp = [new Array(10).fill(1)];
for (let i = 1; i < N; i++) {
dp[i] = [1];
for (let j = 1; j < 10; j++) {
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 10007;
}
}
console.log(dp.pop().reduce((arr, x) => arr + x, 0) % 10007);
9465번 - 스티커
문제 링크 : 스티커
2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.
풀이
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 input = require("fs").readFileSync(filePath).toString().trim().split("\n");
let testCaseNum = +input.shift();
for (let i = 0; i < testCaseNum; i++) {
let n = +input.shift();
let firstScores = input.shift().trim().split(" ").map(Number);
let secondScores = input.shift().trim().split(" ").map(Number);
let dp = Array.from(new Array(n), () => [0, 0, 0]);
dp[0] = [firstScores[0], 0, secondScores[0]];
for (let j = 1; j < n; j++) {
dp[j][0] = Math.max(dp[j - 1][1], dp[j - 1][2]) + firstScores[j];
dp[j][1] = Math.max(dp[j - 1][0], dp[j - 1][2]);
dp[j][2] = Math.max(dp[j - 1][0], dp[j - 1][1]) + secondScores[j];
}
console.log(Math.max(...dp.pop()));
}