문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

예제 입력 1

1
2
3
4

3
26 40 83
49 60 57
13 89 99

예제 출력 1

1

110

예제 입력 2

1
2
3
4

3
1 100 100
100 1 100
100 100 1

예제 출력 2

1

3

예제 입력 3

1
2
3
4

3
1 100 100
100 100 100
1 100 100

예제 출력 3

1

201

예제 입력 4

1
2
3
4
5
6
7

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

예제 출력 4

1

208

예제 입력 5

1
2
3
4
5
6
7
8
9

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

예제 출력 5

1

253

내 코드

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

const [N, ...input] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const n = +N;
const costs = input.map((elem) => elem.split(" ").map(Number));

const MAX = 100001;
let answer = MAX;

let dp = Array.from({ length: n + 1 }, () => [0, 0, 0]);

for (let i = 0; i < 3; i++) {
  for (let j = 0; j < 3; j++) {
    if (i === j) dp[0][j] = costs[0][j];
    else dp[0][j] = MAX;
  }

  for (let j = 1; j < n; j++) {
    dp[j][0] = Math.min(dp[j - 1][1], dp[j - 1][2]) + costs[j][0];
    dp[j][1] = Math.min(dp[j - 1][0], dp[j - 1][2]) + costs[j][1];
    dp[j][2] = Math.min(dp[j - 1][0], dp[j - 1][1]) + costs[j][2];
  }

  for (let j = 0; j < 3; j++) {
    if (i === j) continue;
    answer = Math.min(answer, dp[n - 1][j]);
  }
}

console.log(answer);

해설

RGB 거리 문제와는 다르게 첫번째 선택한 색상을 마지막에서도 선택하면 안되므로 첫번째 선택한 색상을 기억해두도록 접근하자.

예를 들어 첫번째 색상을 R로 선택했다고 하면 나머지 G,B 색상은 선택하지 못하도록 최대값으로 설정해준다.

이후에 다음 집에서는 R을 제외한 나머지 2가지 색상 중 작은 값을 선택하고 해당 집의 색상 비용을 더해줘서 DP 배열을 완성 시켜나간다.

그리하여 DP 배열이 완성되고 나면 DP 배열의 최종 인덱스에 위치한 배열 중 가장 작은 값을 answer 변수에 저장해둔다.

이렇게 첫번째 집을 R로 설정한 경우, G로 설정한 경우, B로 설정한 경우 총 3번을 진행하고 나서 최종적으로 answer 값을 출력해주면 된다.

댓글 공유

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1

1

2

예제 출력 1

1

3

내 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

const N = +require("fs").readFileSync("/dev/stdin").toString().trim();

function fillTile(n) {
  const DP = [0, 0, 3];

  for (let i = 3; i <= n; i++) {
    if (i % 2 !== 0) {
      DP[i] = 0;
      continue;
    }
    let k = i - 2;
    DP[i] = DP[i - 2] * DP[2] + 2;
    while (k >= 2) {
      DP[i] += DP[k - 2] * 2;
      k -= 2;
    }
  }
  return DP[n];
}

console.log(fillTile(N));

해설

우선 n이 홀수인 경우는 경우의 수가 0이다.

그다음에 n이 4인 경우는 직접 그려보았다.

그랬더니 기존 유형을 벗어나는 특이한 모양 2개가 추가되는 것을 알 수 있었다.

DP[4] = DP[2] * 2 + 2 를 알 수 있었다.

이러한 모양은 n이 6인 경우에도 나타났다.

이를 토대로 점화식을 세워보았다.

DP[i] = DP[i-2] * DP[2] + DP[i-4] * 2 + DP[i-6] * 2 + … DP[2] * 2 + 2

1. DP[i-2]에다가 DP[2]의 반복되는 패턴의 경우의 수를 곱해준다.
2. 이후에는 특이한 케이스 2개씩 늘어나는 것만 고려해준다. 예를 들어 DP[2] * 2는 DP[i-2]에서의 특이 케이스 경우의 수를 의미한다.

댓글 공유

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

1
2

10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1

1

54

내 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

const [N, input] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const A = input.split(" ").map(Number);

const DP = [A[0]];
const DPWithRemoval = [A[0]];

for (let i = 1; i < A.length; i++) {
  DP[i] = Math.max(DP[i - 1] + A[i], A[i]);
}

for (let i = 1; i < A.length; i++) {
  DPWithRemoval[i] = Math.max(DP[i - 1], A[i] + DPWithRemoval[i - 1]);
}
const DPMax = Math.max(...DP);
const DPWithRemovalMax = Math.max(...DPWithRemoval);

console.log(Math.max(DPMax, DPWithRemovalMax));

해설

수열 요소 중 한가지를 제거하거나 제거하지 않을 수도 있다. 각각의 경우의 수를 고려해주면 너무 많으니 각 수열의 요소를 제거한 DP 배열을 새로 만들어둔다.

DPWithRemoval은 나 자신을 제거하는 경우 또는 이전 값에서 제거된 경우 2가지 경우의 수가 있다.

1. 나 자신이 제거된 경우라면, 이전 값이 제거되지 않은 DP 배열의 이전값을 그대로 가져온다.
2. 이전 값에서 제거된 경우라면, 이전 값에서 제거된 값을 저장한 DPWithRemoval 배열에서 이전값을 가져와 나 자신을 더한다.

DPWithRemoval[i]는 1,2번의 경우 중 최댓값만 저장하면 된다.

이렇게 하면 수열의 각 숫자마다 제거되었는지 아닌지 경우를 따져서 최댓값만 구할 수 있게된다.

댓글 공유

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제

예제 입력 1

1
2

2

예제 출력 1

1
2

1

예제 입력 2

1
2

10

예제 출력 2

1

3

내 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

const input = +require("fs").readFileSync("/dev/stdin").toString().trim();

const DP = [];
DP[1] = 0;

for (let i = 2; i <= input; i++) {
  const availables = [DP[i - 1]];
  if (i % 2 === 0) {
    availables.push(DP[Math.floor(i / 2)]);
  }
  if (i % 3 === 0) {
    availables.push(DP[Math.floor(i / 3)]);
  }

  DP[i] = 1 + Math.min(...availables);
}

console.log(DP[input]);

DP는 작은 문제부터 해결하여 이를 저장하여 큰 문제를 해결하는 프로그래밍 방식이다.

1. 자연수 2부터 N까지 수가 주어진 3가지 연산으로 1을 만들 수 있는 최소한의 연산 횟수를 담은 배열 DP를 생성한다.
2. 예를 들어 숫자 2는 1을 만들 수 있는 연산횟수가 1회이므로 DP[2] = 1 이다. 그렇다면 DP[6]는 어떻게 알 수 있는가? 바로 숫자 6을 3가지 연산을 수행한 결과값(5,2,3)을 DP 배열에서 찾고 1을 더해주면 된다. DP[6] = 1 + (DP[2], DP[3], DP[5] 중 최솟값)

나는 중간에 2로 나눴을 때와 3으로 나눴을 때를 else if로 하는 바람에 2로 나눠지면 3으로는 못나누도록 코드를 짜서 계속 틀렸다고 나왔었다.

댓글 공유

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제

예제 입력 1

1
2

2

예제 출력 1

1
2

2

예제 입력 2

1
2

9

예제 출력 2

1

55

내 코드

1
2
3
4
5
6
7
8
9
10
11

const input = +require("fs").readFileSync("/dev/stdin").toString().trim();

const DP = [];
DP[1] = 1;
DP[2] = 2;

for (let i = 3; i <= input; i++) {
  DP[i] = (DP[i - 1] + DP[i - 2]) % 10007;
}

console.log(DP[input]);

패턴을 찾아보려고 노력했지만 결국 못찾고 다른 사람 코드를 보았다.. DP는 작은 문제에서 나온 결과물을 가지고 큰 문제를 해결하는 문제이다. 즉, 작은 문제의 결과물을 큰 문제에 결과물에 대입할 수 있는 안목이 필요하다.

위 문제는 2x1 타일을 가장 왼쪽에 세로로 배치했을 때, 2x1 타일을 가장 왼쪽에 가로로 2줄 배치했을 때 경우의 수로 나뉜다.

n = 1인 경우는 1가지이고, n = 2인 경우 2가지를 그림으로 그려본다.

• 즉, 왼쪽에 세로로 2x1을 배치했을 때 경우의 수는 n-1 경우의 수와 같고, 왼쪽에 가로로 2줄 배치했을 때경우의 수는 n-2의 경우의 수와 같다.
• 따라서 DP[n] = DP[n-1] + DP[n-2]가 성립한다.

댓글 공유

문제

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, … 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

예제

예제 입력 1

1
2
3

4
1 5 6 7

예제 출력 1

1
2

10

예제 입력 2

1
2
3

5
10 9 8 7 6

예제 출력 2

1
2

50

예제 입력 3

1
2
3

10
1 1 2 3 5 8 13 21 34 55

예제 출력 3

1
2

55

예제 입력 4

1
2
3

10
5 10 11 12 13 30 35 40 45 47

예제 출력 4

1
2

50

예제 입력 5

1
2
3

4
5 2 8 10

예제 출력 5

1
2

20

예제 입력 6

1
2
3

4
3 5 15 16

예제 출력 6

1

18

내 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(/\s/);
const N = +input.shift();
const prices = input.map(Number);

const DP = new Array(N + 1).fill(0);

for (let i = 1; i <= N; i++) {
  for (let j = 1; j <= i; j++) {
    DP[i] = Math.max(DP[i], DP[i - j] + prices[j - 1]);
  }
}

console.log(DP[N]);

처음에는 반복문 1회만으로 가능할 것이라 생각하여 단일 반복문으로 패턴을 파악하였는데 테케만 통과하고 틀렸다고 나왔다.

그래서 다른 사람 해설을 보고 이해하였다.

ex) N = 4

1. i = 1, DP[4]와 prices[4-1-1]+DP[1] 중 최대값 할당
2. i = 2, DP[4]와 prices[4-2-1]+DP[2] 중 최대값 할당
3. i = 3, DP[4]와 prices[4-3-1]+DP[3] 중 최대값 할당

위 경우의 수를 반복해야하므로 이중 for문이 필요하다는 것을 알게되었다.

댓글 공유

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

• 1+2+1
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

예제

예제 입력 1

1
2
3
4
5

3
4
7
10

예제 출력 1

1
2
3

3
9
27

내 코드

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
34
35
36
37
38
39

// 시간 초과
const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const T = +input.shift();
const nums = input.map(Number);
const N = Math.max(...nums);

// DP[n][k] 는 n을 만들 때 끝의 자리수가 k로 끝나는 경우의 수를 나타낸다. (k = 1,2,3)
const DP = Array.from({ length: N + 1 }, () => new Array(4).fill(0));

DP[1][1] = 1;
DP[1][2] = 0;
DP[1][3] = 0;
DP[2][1] = 0;
DP[2][2] = 1;
DP[2][3] = 0;
DP[3][1] = 1;
DP[3][2] = 1;
DP[3][3] = 1;

nums.forEach((num) => {
  for (let i = 4; i <= num; i++) {
    for (let j = 1; j <= 3; j++) {
      if (j === 1) {
        DP[i][j] = (DP[i - j][2] + DP[i - j][3]) % 1000000009;
      }
      if (j === 2) {
        DP[i][j] = (DP[i - j][1] + DP[i - j][3]) % 1000000009;
      }
      if (j === 3) {
        DP[i][j] = (DP[i - j][1] + DP[i - j][2]) % 1000000009;
      }
    }
  }
  console.log(DP[num].reduce((acc, cur) => (acc + cur) % 1000000009, 0));
});

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
34

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const T = +input.shift();
const nums = input.map(Number);
const N = Math.max(...nums);

// DP[n][k] 는 n을 만들 때 끝의 자리수가 k로 끝나는 경우의 수를 나타낸다. (k = 1,2,3)
const DP = Array.from({ length: N + 1 }, () => new Array(4).fill(0));

DP[1][1] = 1; // 1
DP[1][2] = 0;
DP[1][3] = 0;
DP[2][1] = 0;
DP[2][2] = 1; // 2
DP[2][3] = 0;
DP[3][1] = 1; // 2+1
DP[3][2] = 1; // 1+2
DP[3][3] = 1; // 3

for (let i = 4; i <= N; i++) {
  for (let j = 1; j <= 3; j++) {
    for (let k = 1; k <= 3; k++) {
      if (j === k) continue;
      DP[i][j] += DP[i - j][k] % 1000000009;
    }
  }
}

nums.forEach((num) => {
  console.log(DP[num].reduce((acc, cur) => (acc + cur) % 1000000009, 0));
});

1. DP[n][k]는 n 을 만들 때, 끝의 자리수가 k로 끝나는 경우의 수를 나타낸다. (k = 1,2,3)
2. j가 1이면 k는 1이 아니여야만 가능하다. 왜냐하면 연속해서 올 수 없기 때문이다.
3. DP 저장을 해줄 때에도 1000000009을 나눠주고 합한 것도 나눠줘야하는 이유를 모르겠다.

댓글 공유

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제

예제 입력 1

1
2

1

예제 출력 1

1
2

9

예제 입력 2

1
2

2

예제 출력 2

1

17

내 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

const input = +require("fs").readFileSync("/dev/stdin").toString().trim();

const DP = [
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
];

while (DP.length !== input + 1) {
  DP.push([...Array(10)]);
}

for (let i = 2; i <= input; i++) {
  for (let j = 0; j <= 9; j++) {
    DP[i][j] = ((DP[i - 1][j - 1] || 0) + (DP[i - 1][j + 1] || 0)) % 1000000000;
  }
}

console.log(DP[input].reduce((acc, cur) => (acc + cur) % 1000000000, 0));

• DP[i][j]의 값은 길이가 i인 수가 j(0~9)로 끝나는 모든 경우의 수이다.
• DP 배열을 하드코딩으로 직접 만들어줬다. 왜나하면 초기값 같은 경우는 직접 만드는 편이 더 로직이 간편하기 때문이다. 이후 input의 길이보다 1 더 큰 길이로 DP 배열에 추가하였다.
  • 이렇게 하지 않으면 DP[input]의 값이 존재하지 않는 값이여서 값을 할당할 수가 없다.
• 주어진 테케에서 길이가 1인경우, 길이가 2인 경우의 패턴을 파악하였다.
  • 예를 들어 DP[2][1]인 경우 길이가 2이고 1로 끝나는 경우의 수는 1 앞에 올 수 있는 수는 0,2이다. 이 값이 바로 DP[1][0]과 DP[1][2] 이다.
• 저번 문제에서도 그렇고 왜 10억을 값을 저장할 때 한번, 총합을 구할 때 두번 나눠주는지 이해가 안된다.
• 주의할 점은 끝나는 수가 0인 경우는 이전 숫자로 1만 올 수 있고, 끝나는 숫자가 9인 경우는 이전 숫자로 8만 올 수 있는 것을 고려해준 것이 바로 || 논리 연산자 부분이다.

댓글 공유

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

예제

예제 입력 1

1
2

3

예제 출력 1

1

2

내 코드

1
2
3
4
5
6
7
8
9

const input = +require("fs").readFileSync("/dev/stdin").toString().trim();

const DP = [BigInt(0), BigInt(1)];

for (let i = 2; i <= input; i++) {
  DP[i] = DP[i - 2] + DP[i - 1];
}

console.log(DP[input] + "");

• 처음에는 길이가 i인 수가 0,1로 끝나는 수를 나타내기 위해 DP[i][0], DP[i][1]로 배열을 구성하였는데, 점화식을 알아내고 나니 DP[i] = DP[i-2] + DP[i-1]로 계산하기 위해 DP을 1차원 배열로 바꿨다.
• N이 90까지 가능하므로 이 경우 수가 매우 커져 number의 범위가 넘어가는 경우가 있을 수 있기 때문에 BigInt()로 값을 계산해줘야 한다.

댓글 공유

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제

예제 입력 1

1
2
3

6
10 20 10 30 20 50

예제 출력 1

1

4

내 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

const [N, a] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const A = a.split(" ").map(Number);

const DP = Array.from({ length: N }, () => 1);

for (let i = 1; i < N; i++) {
  for (let j = 0; j < i; j++) {
    if (A[j] < A[i]) {
      DP[i] = Math.max(DP[i], DP[j] + 1);
    }
  }
}

console.log(Math.max(...DP));

• 처음 모두 자신의 길이를 자신을 포함하므로 1로 설정해준다.
• 만약 i 번째 수가 i보다 작은 번째의 수보다 크다면 DP[i]는 이전 DP값에 1을 더해준 것과 기존 DP[i]값 중 큰 값을 저장해둔다.
• ex) A = [10,20,10,30,20,50]이고 DP[1]을 계산하면, A[0] < A[1] 이므로 DP[1] = DP[0] + 1이다.
  • 왜냐하면 DP는 자신의 길이를 나타내는 것인데 이전 수보다 크다는 것은 자기 자신을 수열로 포함시킬 수 있다는 뜻이므로 +1을 해주는 것이다. 또한, 자신 보다 작은 수의 DP가 여러개 일 수도 있으므로 반복문을 돌면서 이들 중 최댓값만 저장해주면 된다.

댓글 공유