[백준 15990번 1, 2, 3 더하기 5 - node.js] [알고리즘 기초 1/2]

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

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

 

문제

 

정수 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로 나눈 나머지를 출력한다.

 

예제 입출력

 

입력	출력
3 4 7 10	3 9 27

 

풀이[node.js]

 

 

728x90

마지막 자리의 수가 연속된 값이 되면 안되기 때문에, 우리는 1, 2, 3 중 마지막 자리가 어떤 숫자로 끝나는지 알아야합니다.

그래서, 0, 1, 2, 3의 각각의 숫자에서 합은 나타낸 숫자들의 마지막 수가 1, 2, 3 별로 몇개가 있는지를 arr에 담아주었습니다.

1인 경우, 마지막 수가 1이 1개, 2, 3은 0개이고,

2인 경우, 마지막 수가 2가 1개, 1, 3은 9개,

3인 경우, 마지막 수가 1, 2, 3 각각 모두 1가지 씩입니다.

우리는 결국 이전의 1, 2, 3 더하기와 마찬가지로 자릿수를 만들기 위해,

[어떤 자릿수 경우의 수] + 1

[어떤 자릿수 경우의 수] + 2

[어떤 자릿수 경우의 수] + 3

이렇게 값을 구해야 합니다.

우리는 각 자릿수별로 마지막에 오는 숫자 1,2,3이 몇개가 있는지 arr에 담겨있기 때문에, +1을 할 경우에는 끝에 2, 3이 오는 경우의 수만, +2를 할 경우에는 끝에 1, 3이 있는 경우의 수만, +3을 할 경우에는 끝에 1, 2가 있는 경우의 수만 더해주면 됩니다. (아래 그림 참고)

그렇기에, arr[i]는 앞의 arr의 [2, 3가짓수 더한 값, 1,3 가짓수를 더한 값, 1,2 가짓수를 더한 값]으로 넣어주면 됩니다.

각 가짓수별로 1000000009를 나눈 값을 대입해줍니다.

그리고 마지막에, 들어온 값들의 가짓수를 reduce함수를 사용하여 가산한 후, 다시 1000000009로 나눠서 출력해주면 됩니다.

각각의 1000000009로 나눈 값들을 다시 더했기 때문에 다시 한번 1000000009로 나눠서 출력해줘야합니다.

var fs = require('fs');
var inputs = fs.readFileSync('/dev/stdin').toString().split('\n').map(v=>Number(v)).filter(v=> v != 0);
var cases = Number(inputs[0]);
inputs.shift();
var max = Math.max(...inputs);
var arr = [[0,0,0], [1,0,0], [0,1,0], [1,1,1]];
for(var i=4; i<=max; i++){
    arr[i] = [(arr[i-1][1] + arr[i-1][2]) % 1000000009, (arr[i-2][0] + arr[i-2][2]) % 1000000009, (arr[i-3][0] + arr[i-3][1]) % 1000000009];
} 
for(var k=0; k<cases; k++){
    console.log(arr[inputs[k]].reduce((a,v)=> a+v, 0) % 1000000009);
}