10844번 - 쉬운 계단 수
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.
풀이
배열로 자리수를 구별해서 저장하면 쉽게 해결할 수 있습니다.
0은 1만 가능하며 9는 9만 가능하므로 따로 처리해줍니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let input = require("fs").readFileSync(filePath).toString().trim();
let answer = Array.from(new Array(Number(input) + 1), () =>
new Array(10).fill(0)
);
answer[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1];
for (let i = 2; i <= input; i++) {
answer[i][1] += answer[i - 1][0] % 1000000000;
answer[i][8] += answer[i - 1][9] % 1000000000;
for (j = 1; j <= 8; j++) {
answer[i][j + 1] += answer[i - 1][j] % 1000000000;
answer[i][j - 1] += answer[i - 1][j] % 1000000000;
}
}
console.log(answer.pop().reduce((acc, x) => acc + x, 0) % 1000000000);
2193번 - 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.
- 이친수는 0으로 시작하지 않는다.
- 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다.
하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.
N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.
첫 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let input = require("fs").readFileSync(filePath).toString().trim();
let answer = Array.from(new Array(Number(input) + 1), () =>
new Array(2).fill(0)
);
answer[1] = [0, 1];
for (let i = 2; i <= input; i++) {
answer[i][0] = answer[i - 1][0] + answer[i - 1][1];
answer[i][1] = answer[i - 1][0];
}
console.log(answer.pop().reduce((acc, x) => acc + x, 0));
값이 커서 오답처리 되는 듯합니다.
다른 풀이
값이 너무 커서 오답처리되므로 BigInt로 값들을 감싸줍니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let input = require("fs").readFileSync(filePath).toString().trim();
let answer = Array.from(new Array(Number(input) + 1), () =>
new Array(2).fill(0)
);
answer[1] = [0, 1];
for (let i = 2; i <= input; i++) {
answer[i][0] = BigInt(answer[i - 1][0]) + BigInt(answer[i - 1][1]);
answer[i][1] = BigInt(answer[i - 1][0]);
}
answer = answer.pop();
answer = BigInt(answer[0]) + BigInt(answer[1]);
console.log(answer.toString());
다른 풀이 2
값들을 잘 보면 1, 1, 2, 3, 5 순으로 피보나치 수열에 해당합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let input = require("fs").readFileSync(filePath).toString().trim();
let answer = Array.from(new Array(Number(input) + 1), () => 0);
answer[1] = 1;
answer[2] = 1;
for (let i = 3; i <= input; i++) {
answer[i] = BigInt(answer[i - 1]) + BigInt(answer[i - 2]);
}
console.log(answer.pop().toString());
11053번 - 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
풀이
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 input = require("fs").readFileSync(filePath).toString().trim().split("\n");
let n = Number(input[0]);
let inputs = input[1].split(" ").map(Number);
let dp = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
let max = 0;
for (let j = 0; j < i; j++) {
if (inputs[j] < inputs[i] && max < dp[j]) {
max = dp[j];
}
}
dp[i] = max + 1;
}
console.log(Math.max(...dp));
14002번 - 가장 긴 증가하는 부분 수열 4
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
첫 풀이
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
27
28
29
30
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let input = require("fs").readFileSync(filePath).toString().trim().split("\n");
let n = Number(input[0]);
let inputs = input[1].split(" ").map(Number);
let dp = Array.from({ length: n }, () => []);
dp[0] = [inputs[0]];
let maxArr = [];
for (let i = 1; i < n; i++) {
let tmp = [];
for (let j = 0; j < i; j++) {
if (inputs[j] < inputs[i] && tmp.length < dp[j].length + 1) {
tmp = Array.from(dp[j]);
tmp.push(inputs[i]);
if (tmp.length > maxArr.length) maxArr = tmp;
}
}
dp[i] = tmp.length ? tmp : [inputs[i]];
}
console.log(Number(maxArr.length));
console.log(maxArr.join(" "));
다른 풀이
dp 배열에는 앞선 11053번 문제처럼 갯수를 담고 가장 큰 index 값을 따로 저장합니다.
해당 index 값을 이용해 arr 배열에 따로 저장해줍니다.
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
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let input = require("fs").readFileSync(filePath).toString().trim().split("\n");
let n = Number(input[0]);
let inputs = input[1].split(" ").map(Number);
let dp = Array.from({ length: n }, () => 0);
let arr = [];
for (let i = 0; i < n; i++) {
let max = 0;
let maxIdx = -1;
for (let j = 0; j < i; j++) {
if (inputs[i] > inputs[j] && dp[j] > max) {
max = dp[j];
maxIdx = j;
}
}
dp[i] = max + 1;
arr[i] = maxIdx !== -1 ? [...arr[maxIdx], inputs[i]] : [inputs[i]];
}
let answer = Math.max(...dp);
console.log(answer);
console.log(arr[dp.indexOf(answer)].join(" "));
1912번 - 연속 합
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
풀이
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().split("\n");
let n = Number(input[0]);
let inputs = input[1].split(" ").map(Number);
let dp = Array.from({ length: n }, () => 0);
dp[0] = inputs[0];
for (let i = 1; i < n; i++) {
if (dp[i - 1] < 0) dp[i] = Math.max(dp[i - 1] + inputs[i], inputs[i]);
else {
dp[i] = dp[i - 1] + inputs[i];
}
}
console.log(Math.max(...dp));
1699번 - 제곱수의 합
첫 풀이
입력 수보다 작은 수 중 가장 큰 제곱수를 뺴는 경우는 반례가 존재합니다.
43의 경우 6^2 + 2^2 + 1^2 + 1^2 + 1^2 로 5개가 나오지만 5^2 + 3^2 + 3^2 로 3가지도 나올 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let input = require("fs").readFileSync(filePath).toString().trim();
let num = Number(input);
let cnt = 0;
while (num) {
let n = Math.floor(Math.sqrt(num));
num -= Math.pow(n, 2);
cnt++;
}
console.log(cnt);
다른 풀이
dp로 문제를 해결해보겠습니다.
입력 값을 제곱수들의 합으로 나타내므로 a^2 + b^2 + … + z^2 형태로 나타날 것입니다.
입력 값에따른 최소 갯수를 배열로 저장해보겠습니다.
DP[n]에는
DP[n] = DP[n - a^2] + 1,
DP[n] = DP[n - b^2] + 1,
…
DP[n] = DP[n - z^2] + 1
중 가장 작은 수가 저장될 것입니다.
초기값으로 DP[0] = 0, DP[1] = 1을 주고 반복문을 돌려 해결합니다.
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 dp = new Array(num + 1).fill(num);
dp[0] = 0;
dp[1] = 1;
for (let i = 1; i <= num; i++) {
for (let j = 1; j ** 2 <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j ** 2] + 1);
}
}
console.log(dp[num]);