백준 js - 9095번

<문제>

https://www.acmicpc.net/problem/9095

 

 

 

 

<문제 핵심>

 

1.  다이나믹 프로그래밍(동적 계획법)을 사용하는 문제였고 DP의 핵심은 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장하여야 한다.  occation[1], occation[2], occation[3] 일 때 숫자를 조합하여 각 숫자를 만들 수 있는 경우의 수를 구한다. 각각 1, 2, 4 라는 경우의 수가 나오는데 이때 점화식을 유출할 수 있다.

 

occation[4] = occation[i-3] + occation[i-2] + occation[i-1] 

 

이처럼 숫자 4를 만들기 위해 조합할 수 있는 경우의 수는 7가지 이고 해당 경우의 수는 이전에 구한 occation[1], occation[2], occation[3]을 통해서 구할 수 있다. 

 

 

2. 경우의 수

 

1을 1,2,3을 이용해 만드는 경우의 수 : 1

2를 1,2,3을 이용해 만드는 경우의 수 : 2

3를 1,2,3을 이용해 만드는 경우의 수 : 4

4를 1,2,3을 이용해 만드는 경우의 수 : 7

 

<문제 풀이과정 및 순서도>

1. 입력받은 뒤 1부터 3까지의 수를 만들기 위해 조합할 수 있는 경우의 수를 미리 occation 배열에 담는다. 

 

2. 4부터 반복문을 돌리게 되는데 점화식을 파악한 뒤 점화식과 규칙에 맞추어 반복문을 순회

 

3. 4, 7, 10에 해당하는 인덱스의 값을 출력한다.

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const t = Number(input.shift());
const testCase = input.map(Number);

//0~3 인덱스에 값을 미리 설정
const occation = [0, 1, 2, 4];

for (let i = 4; i <= Math.max(...testCase); i++) {
  occation[i] = occation[i - 3] + occation[i - 2] + occation[i - 1];
}

testCase.forEach((value) => {
  console.log(occation[value]);
});