[JavaScript] 백준 11727번 문제 풀이

DP 점령 2일차.

지난 포스팅에 간단하게 DP에 대한 특징을 정리했습니다.

그것을 기억하면서 이 문제를 풀어봅시다.

2023.09.13 - [알고리즘 PS/Javascript] - [JavaScript] 백준 1463번 문제

[JavaScript] 백준 1463번 문제

 

처음에 주어진 것은 

 

1인 경우에는 1가지이고,
2인 경우에는 3가지가 나오는 구나.

DP의 가장 큰 특징 중 하나는 작은 단위로부터 문제를 해결하려는 것입니다.

그래서 작은 단위에서부터 규칙을 찾을 수 있으면 문제는 쉽게 풀 수 있습니다.

규칙 찾기

2일 때, 3가지이고, 

3일 때, 5가지가 나옵니다.

4일 때, 11가지가 나옵니다.

 

조금 더 밝은 파란색에 집중을 하신다면 규칙을 찾을 수 있습니다.

 

3일 때부터 자세히 보면, 밝은 파란색으로 색이 칠해진 것을 빼고 봅시다.

처음에 3개는 2일 때 경우의 수입니다. 나머지 2개는 1일 때 경우의 수입니다.

 

그리고, 4일 때를 자세히 봅시다. 첫 번째 줄에서 밝은 파란색을 빼고 본다면 3일 때의 경우의 수입니다.

두 번째 줄에서 밝은 파란색을 빼고 본다면 나머지 6개는 2일 때 경우의 수입니다.

 

결론

즉, 위의 그림과 같은 결론을 얻을 수 있습니다.

 

const stdin = require('fs').readFileSync(0, 'utf8').trim().split('\n');
const N = +stdin[0];
const dp = Array(1001).fill(0);
dp[1] = 1;
dp[2] = 3;

for (let i = 3; i <= N; i++) {
  dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
}

console.log(dp[N]);