문제

수열 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
2

4
10 20 30 50

내 코드

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 [N, input] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const A = input.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);
    }
  }
}

const LIS = Math.max(...DP);

let LIS_Array = [];
for (let i = 0; i < N; i++) {
  const index = DP.findIndex((elem) => elem === i + 1);
  LIS_Array.push(A[index]);
}

console.log(LIS);
console.log(LIS_Array.join(" "));

• 기존 LIS를 구하는 로직에서 DP에 해당하는 LIS뿐만 아니라 그 때의 배열까지 생성해주도록 하였다.
• 처음 배열 길이만큼 반복문을 순회하면서 DP값에서 Index를 찾는다. 해당 index의 A 수열의 값을 넣어준다.
• 왜 틀렸는지 이유를 모르겠어서 해설을 보게되었다.

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

const [N, input] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const A = input.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);
    }
  }
}

let LIS = Math.max(...DP);
let LIS_Array = [];

for (let i = N - 1; i >= 0; i--) {
  if (DP[i] === LIS) {
    LIS_Array = [A[i], ...LIS_Array];
    LIS--;
  }
}

console.log(LIS_Array.length);
console.log(LIS_Array.join(" "));

• 이전 내 코드는 findIndex 메서드로 제일 앞에서 부터 해당 인덱스를 찾아주도록 하였다. 하지만 이런 경우 반례가 생긴다. 왜냐하면 내가 처음에 DP의 초기값을 모두 1로 설정해두었기 때문에 LIS_Array의 배열의 데이터가 이상하게 들어올 수 있다

반례

N = 14, A = [10, 12, 1, 3, 5, 6, 7, 10, 12, 2, 4, 7, 10, 12]

• findIndex로 앞에서부터 찾았을 경우: LIS_Array = [10, 12, 5, 6, 7, 10, 12]
• 반복문 역순으로 찾았을 경우: LIS_Array = [1, 3, 5, 6, 7, 10, 12]

댓글 공유

문제

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제

예제 입력 1

1
2
3

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

예제 출력 1

1
2

33

예제 입력 2

1
2
3

10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2

1
2

14

예제 입력 3

1
2
3

5
-1 -2 -3 -4 -5

예제 출력 3

1

-1

내 코드

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

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

let DP = Array.from({ length: n }, () => 0);
if (A[0] < 0) {
  DP = Array.from({ length: n }, () => A[0]);
}

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

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

• 처음엔 연속되었다고 하여서 2연속만 생각했었다. 하지만 2번째 예제에서는 연속된 숫자가 3, 4, -4, 6, 5 이렇게 구하여 총합이 14이다.
• 0번째부터 i번째 까지 합을 저장하여 이전값과 비교하여 최댓값을 저장해준다.
• 즉, 01, 02, 03, … 09번째의 합중 최대값만 DP[0]에 저장해준다. 이렇게 0번째부터 9번째 DP를 구하였다.
• 그리고 첫번째가 음수의 경우는 DP를 초기값으로 모두 설정해주었다.
• 하지만 시간 초과가 떴다.

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

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

const DP = Array.from({ length: n }, () => A[0]);

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

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

• DP는 초기 값으로 설정해준다.

1. DP[0] = A[0]
2. DP[1]은 DP[0] + A[1] 과 A[1] 중에 최대값을 저장한다. 왜냐하면 A[1] 이전까지의 연속된 숫자들의 합이 양수라면 A[1] 보다 크지만 음수인 경우는 A[1]부터 시작하는 것이 크기 때문이다.

댓글 공유

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

예제

예제 입력 1

1
2

7

예제 출력 1

1
2

4

예제 입력 2

1
2

1

예제 출력 2

1
2

1

예제 입력 3

1
2

4

예제 출력 3

1
2

1

예제 입력 4

1
2

11

예제 출력 4

1
2

3

예제 입력 5

1
2

13

예제 출력 5

1

2

내 코드

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

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

const DP = Array.from({ length: input + 1 }, (_, i) => i);

for (let i = 4; i <= input; i++) {
  for (let j = 1; j <= Math.sqrt(i); j++) {
    const sqrt = Math.sqrt(i);
    if (sqrt === parseInt(sqrt)) {
      DP[i] = 1;
    } else {
      DP[i] = Math.min(DP[i], DP[i - j ** 2] + 1);
    }
  }
}

console.log(DP[input]);

• 처음에는 단순히 초기값을 가지고 다음값을 구하는 식으로만 했었는데, 이렇게 할 경우 최소항을 비교하여 저장하면서 진행할 수 없다고 판단하여 2중 for문을 사용하였다.
• 그 결과, 각 DP 마다 해당 index의 제곱근을 빼준 숫자의 DP에 +1 해준 것과 현재 DP를 비교했다.

ex) input = 18이라면, DP[18] = 18인 상태로 시작한다.

1. j = 1 인 경우, DP[17] + 1 = 3이므로, DP[18] = 3를 저장한다.
2. j = 2 인 경우, DP[14] + 1 = 4이므로, 이전 값을 그대로 둔다.
3. j = 3 인 경우, DP[9] + 1 = 2 이므로, DP[18] = 2를 저장한다.
4. j = 4 인 경우, DP[2] + 1 = 3 이므로 이전 값을 그대로 둔다.

j는 제곱근 이전 까지만 순회를 하므로 순회를 종료하고 DP값을 출력한다.

따라서, DP[18] = 2 로 (9+9) 이렇게 답을 구할 수 있다.

댓글 공유

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < … Sk-1 < Sk > Sk+1 > … SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 입력 1

1
2

10
1 5 2 1 4 3 4 5 2 1

예제 출력 1

1

7

내 코드

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

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

function LBS(arr) {
  const N = arr.length;
  const DP_inc = Array.from({ length: N }, () => 1);
  const DP_dec = Array.from({ length: N }, () => 1);

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

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

  const DP = [];
  for (let i = 0; i < N; i++) {
    DP.push(DP_inc[i] + DP_dec[i] - 1);
  }

  return Math.max(...DP);
}

console.log(LBS(A));

해설

1. 수열의 시작 부분부터 해당 index의 증가하는 부분수열 길이를 구한다.
2. 수열의 마지막 부분부터 해당 index의 감소하는 부분수열의 길이를 구한다.
3. 증가하는 부분 수열 길이와 감소하는 부분 수열의 길이를 더하여 가장 큰 값의 길이를 구하면 된다.

단, 이 때 기본값으로 세팅한 길이 1이 2번 더해진 것이므로 1을 빼줘야한다.

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

// 나의 오답
function LBS(arr) {
  const N = arr.length;
  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);
      }
    }
    for (let k = i + 1; k < N; k++) {
      if (A[k] >= A[k - 1]) break;

      DP[i] = Math.max(DP[i], DP[i] + 1);
    }
  }

  return Math.max(...DP.map((elem) => elem - 1));
}

console.log(LBS(A));

처음에는 감소하는 부분 수열을 구할 때, 역순으로 시작하지 않고 증가하는 부분 수열 구할 때 새로운 반복문으로 해당 index부터 시작하는 감소하는 부분 수열을 구하였는데 이는 DP라는 배열 하나를 가지고 반복문을 돌렸기 때문에 제대로 동작하지 않고 저장값이 꼬여버릴 수 있다.

댓글 공유

문제

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

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

입력

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

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

출력

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

예제 입력 1

1
2

6
10 30 10 20 20 10

예제 출력 1

1

3

내 코드

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

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

function LDS(arr) {
  const N = arr.length;
  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);
      }
    }
  }
  return Math.max(...DP);
}

console.log(LDS(A));

해설

지난 번에 가장 긴 증가하는 부분수열과 조건문만 수정하면 되는 문제였다.

DP는 A 수열의 index에서 감소하는 부분 수열의 길이를 저장한다.

DP의 해당 index와 이전 index까지의 수열 요소와 비교하여 이전 index가 더 작다면, DP값을 갱신해주는 문제이다.

댓글 공유

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

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

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

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

예제 입력 1

1
2

10
1 100 2 50 60 3 5 6 7 8

예제 출력 1

1

113

내 코드

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

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

function maxIncreasingSubArray(A) {
  const n = A.length;
  const DP = [...A];

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (A[i] > A[j] && DP[i] < DP[j] + A[i]) {
        DP[i] = DP[j] + A[i];
      }
    }
  }
  return Math.max(...DP);
}

console.log(maxIncreasingSubArray(A));

풀이

1. DP는 해당 인덱스까지 가장 긴 부분수열의 합을 나타낸다. 이를 계산하기 편하게 하기 위해 DP에 A 수열의 값을 spread 문법으로 복사해준다.

2. 어짜피 DP[0]은 1로 확정이므로 i(인덱스)가 1부터 반복문을 순회한다.
   이는 DP에 값을 저장하기 위한 반복문이다.

3. i 이전까지 수열 값과 A[i]값을 비교하여 A[i]가 A[j]보다 크고 DP[i] 값이 DP[j]+A[i] 보다 작으면 증가하는 부분 수열에 포함될 수 있다.

그렇기 때문에 해당 DP[i]값을 새로운 값으로 갱신해준다.

예시

1

const A = [1, 100, 2, 50, 60, 3, 5, 6, 7, 8];

1. i = 1 && j = 0 일 때

• A[1] = 100, A[0] = 1이므로 A[i] > A[j] 조건 만족한다
• DP[1] < DP[0] + A[1] 만족하므로 DP[1] = DP[0] + A[1]로 갱신

1

DP = [1, 101, 2, 50, 60, 3, 5, 6, 7, 8];

2. i = 2 이고

2.1. j = 0 일 때

• A[2]=2, A[0] = 1 이므로 A[i] > A[j] 조건 만족한다.
• DP[2] < DP[0] + A[2] 만족하므로 DP[2] = DP[0] + A[2]로 갱신

2.2. j = 1 일 때,

• A[2]=2, A[1] = 100 이므로 A[i] > A[j] 조건 만족하지 못한다.

1

DP = [1, 101, 3, 50, 60, 3, 5, 6, 7, 8];

즉, 0번째부터 해당 인덱스까지 수열의 두 수를 비교하고 DP에 저장된 값도 비교하여 둘다 만족하면 DP 값을 갱신하는 것이다.

댓글 공유

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

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

예제

예제 입력 1

1
2

20 2

예제 출력 1

1
2

21

예제 입력 2

1
2

6 4

예제 출력 2

1

84

내 코드

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

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

const DP = Array.from({ length: N + 1 }, (_, i) => {
  if (i === 1) return Array.from({ length: K + 1 }, (_, i) => i + 1);
  return new Array(K + 1).fill(1);
});

for (let i = 2; i <= N; i++) {
  for (let j = 1; j <= K; j++) {
    DP[i][j] = (DP[i - 1][j] + DP[i][j - 1]) % 1000000000;
  }
}

console.log(DP[N][K - 1]);

• ✏️ N = 1인 경우 K = 1,2,3 …200 경우의 수를 생각해보았다.
  • ❗️ 1개의 수로 1을 만들 수 있는 경우의 수는 1가지이다.
  • 2개의 수로 1을 만들 수 있는 경우의 수는 0+1, 1+0으로 2가지이다.
  • 3개의 수로 1을 만들 수 있는 경우의 수는 0+0+1, 0+1+0, 1+0+0으로 3가지이다…
• N = 2인 경우 K = 1,2,3 …200 경우의 수를 생각해보았다.
  • ❗️ 1개의 수로 2를 만들 수 있는 경우의 수는 1가지이다.
  • 2개의 수로 2를 만들 수 있는 경우의 수는 1+1, 2+0, 0+2로 3가지이다.
  • 3개의 수로 2를 만들 수 있는 경우의 수는 1+1+0, 1+0+1, 0+1+1, 2+0+0, 0+2+0, 0+0+2로 6가지이다…

❗️의 조건을 가지고 DP[N][k] 2차원 배열에서, DP[N][1] = 1인 것을 알 수 있다.

✏️의 조건을 가지고 DP[1][k] = K 인 것을 알 수 있다.

위와 같은 점화식을 발견하였고 그에 알맞은 식을 만들었다.

댓글 공유

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

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

입력

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

출력

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

예제

예제 입력 1

1
2
3
4
5

3
4
7
10

예제 출력 1

1
2
3

7
44
274

내 코드

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

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

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

input.forEach((num) => {
  for (let i = 4; i <= num; i++) {
    DP[i] = (DP[i - 3] + DP[i - 2] + DP[i - 1]) % 1000000009;
  }
  console.log(DP[num]);
});

• 1을 1,2,3으로 만들 수 있는 경우의 수, 2를 1,2,3으로 만들 수 있는 경우의 수, 3을 1,2,3으로 만들 수 있는 경우의 수는 직접 구할 수 있어서 구하였다.
• 4부터는 맨 마지막에 1,2,3이 오는 경우의 수를 나누어서 생각하였다.
  • 맨 마지막에 1이 오는 경우 ⇒ 1+1+1+1, 1+2+1, 2+1+1, 3+1 ⇒ DP[4-1]
  • 맨 마지막에 2가 오는 경우 ⇒ 1+1+2, 2+2 ⇒ DP[4-2]
  • 맨 마지막에 3이 오는 경우 ⇒ 1+3 ⇒ DP[4-3]

하지만 위와 같은 방법으로 하게되면 n이 1,000,000이 주어졌을 때, 반복문은 n-3회 진행하므로 시간초과가 난다. 심지어 테스트 케이스 수가 T개 주어지는 만큼 n-3회 반복해야 하므로 매우 오래걸릴 수도 있게된다.

즉, input 값 중에서 가장 큰 값으로 반복문 한번만 순회한 다음, 완성된 DP 배열에서 해당 값을 찾는 식으로 방법을 바꿨다.

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

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

function solution(n, arr) {
  if (n < 4) return arr[n - 1];

  for (let i = 4; i <= n; i++) {
    DP[i] = (DP[i - 3] + DP[i - 2] + DP[i - 1]) % 1000000009;
  }
  return arr;
}

const DP = [0, 1, 2, 4];
solution(Math.max(...input), DP);

input.forEach((num) => {
  console.log(DP[num]);
});

댓글 공유

문제

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

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

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

입력

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

출력

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

예제

예제 입력 1

1
2
3
4
5

3
26 40 83
49 60 57
13 89 99

예제 출력 1

1
2

96

예제 입력 2

1
2
3
4
5

3
1 100 100
100 1 100
100 100 1

예제 출력 2

1
2

3

예제 입력 3

1
2
3
4
5

3
1 100 100
100 100 100
1 100 100

예제 출력 3

1
2

102

예제 입력 4

1
2
3
4
5
6
7
8

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

예제 출력 4

1
2

208

예제 입력 5

1
2
3
4
5
6
7
8
9
10

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

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

function solution(n, rgb) {
  const DP = Array.from({ length: n + 1 }, () => new Array(3).fill(0));
  DP[1] = rgb[0];
  for (let i = 2; i <= n; i++) {
    DP[i][0] = Math.min(DP[i - 1][1], DP[i - 1][2]) + rgb[i - 1][0];
    DP[i][1] = Math.min(DP[i - 1][0], DP[i - 1][2]) + rgb[i - 1][1];
    DP[i][2] = Math.min(DP[i - 1][1], DP[i - 1][0]) + rgb[i - 1][2];
  }
  console.log(Math.min(...DP[n]));
}

solution(+N, input);

• 처음에는 1번째 집이 R,G,B를 선택하는 경우의 수를 구하고 이를 이 중 가장 작은 것을 가지고 다음 집을 구한다고 생각했다. 생각은 했는데 이를 코드로 어떻게 짜야할지 생각을 못해서 경우의수를 일일히 적어보고 패턴을 찾아보려고 했다.
• 하지만 못찾아서 다른 사람의 해설을 참고하였다. 문제가 복잡해보이지만 단순하게 생각하면 인접한 집끼리는 같은 색상을 가질 수 없다는 것이 전부이다.

우선, DP 배열을 만들고 해당 DP[i][0]은 i번째 집을 Red로 색칠하는 비용을 저장한다.

• DP[1] = input[0] 이 성립한다.
• 이후 i = 2 부터 반복문을 진행한다.
  1. DP[2]가 R로 색칠될 경우의 비용을 저장한다. ⇒ DP[2]가 R 이기 위해서는 DP[1]에서 G, B로 색칠되어야만 가능하다. 즉 DP[1]에서 G, B를 칠하는 비용 중 최소값을 구하고 이에 input의 2번째 집에 해당하는 비용 중 R을 색칠하는 비용을 더해주면 DP[2][0] 즉, 2번째 집을 R로 칠할 때 최소 비용을 구할 수 있다.
  2. DP[2][1]은 이전 집에서 R, B 중 최소값에다가 input의 2번째 집에 해당하는 비용 중 G을 색칠하는 비용을 더해주면 DP[2][1]의 최솟값을 구할 수 있다.

댓글 공유

문제

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

예제

예제 입력 1

1

4

예제 출력 1

1

41

내 코드

N = 3 까지의 경우의 수를 적고나서 점화식을 생각해보았다. 처음에는 DP[i] = 2*DP[i-1] + (2**(i-1) - 1) 이라고 생각했는데 오답이였다.

다시 점화식을 세웠다.

1

DP[i] = 2 * DP[i - 1] + DP[i - 2];

1
2
3
4
5
6
7
8
9

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

const DP = [0, 3, 7, 17];

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

console.log(DP[input]);

위 처럼 직접 경우의 수를 다 계산할 수 있었지만, DP를 2차원 배열로 설정하고 첫번째 칸에 공백이 오는경우, 좌측에 사자 채우는 경우, 우측에 사자 채우는 경우를 나눠서 구해볼 수 도 있을 것 같다.

댓글 공유