[JS][백준]15990_1, 2, 3 더하기 5

문제 번호

15990번: 1, 2, 3 더하기 5

 

 

알고리즘 분류

• 다이나믹 프로그래밍

 

문제 풀이

 처음에는 점화식을 세워서 풀이를 진행하려고 했다. 하지만 이렇다 할 규칙을 찾아내지 못하여서 2차원 배열을 사용한 DP알고리즘을 사용하면 더 쉽고 직관적인 풀이가 가능하다는 것을 알았다.

 

 처음에 생각해본것은 DP알고리즘을 사용할 것이기 때문에 N을 만들기위해서 N-1, N-2, N-3 들을 어떻게 활용할 것인가 였다. N-1 에서 N에 영향을 줄 수 있는 방법은 1을 더하는 것뿐이다. 그리고 하나 더 고려해야 할 점은 같은 수는 연속해서 올 수 없다는 점이다. 그래서 DP[i][j]는 i를 만들 때 j로 끝나는 경우의 수라고 생각해봤다.

	1	2	3
1	1	0	0
2	0	1	0
3	1	1	1
4	X	ㅇ	ㅇ
5	ㅇ
6	필요		필요
7
8		필요2개를 합쳐서 이곳을 알 수 있다.
9

 세로축이 i, 가로축이 j라고 생각해보자. DP[1][1] 은 1을 만들 때 1로 끝나는 경우의 수 이므로 1이다. DP[2][2]도 마찬가지로 1이다. DP[3][1]은 2,1로 3을 만드는 경우(1로 끝)를 의미한다. DP[3][2]는 1,2로 3을 만드는 경우(2로 끝)를 의미한다. 그럼 X 표시는 어떻게 구할까?

 DP[4][1]은 DP[3][2] + DP[3][3] 이다. 왜냐하면 DP[4][1]은 1로 끝나기 때문에 DP [3][?]에서 1로 끝나는 경우는 사용할 수 없다. 연속해서 같은 숫자를 사용할 수 없기 때문이다. '.... 1 ' 이런 경우는 사용할 수 없고 ....2 나 ...3 인경 우만 사용할 수 있다는 뜻이다. 즉 우리는 마지막에 1을 더하면서 4를 만들 수 있는 경우를 찾는데, 이때 DP[3][2]와 DP[3][3]을 참고하여서 3을 만들때 2와 3으로 끝나는 경우에 1만 더 붙여서 4를 완성할 거다. 

 DP[4][2]와 DP[4][3]의 경우도 위와 같은 원리로 채워주면 된다. 

  dp[1][1] = 1;
  dp[2][2] = 1;
  dp[3][1] = 1, dp[3][2] = 1, dp[3][3] = 1;
  for (let i = 4; i <= 100000; i++) {
    dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % div;
    dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % div;
    dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % div;
  }

 1,2,3 과 인덱스를 맞춰주기 위해서 필요 없는 1줄을 더 추가한 배열을 사용하였다.

 

전체 코드

const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
const div = 1000000009;

function sol(dp) {
  dp[1][1] = 1;
  dp[2][2] = 1;
  dp[3][1] = 1, dp[3][2] = 1, dp[3][3] = 1;
  for (let i = 4; i <= 100000; i++) {
    dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % div;
    dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % div;
    dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % div;
  }
}
function main() {
  let answer = '';

  let T = +input[0];
  let dp = new Array(100001).fill(null).map(_ => new Array(4).fill(0));

  sol(dp);
  console.log(dp)
  for (let i = 1; i <= T; i++) {
    let n = +input[i];
    answer += (dp[n][1] + dp[n][2] + dp[n][3]) % div + '\n';
  }

  console.log(answer.trim())
}
main();

특이사항