[알고리즘] 백준 9095번: 1, 2, 3 더하기 (완전탐색,재귀) W_node.js

문제

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

9095번: 1, 2, 3 더하기

정수 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은 양수이며 11보다 작다.

3
4
7
10

출력예시

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

7
44
274

풀이

//백준 9095 
//1,2,3 더하기

/* input
3
4
7
10
*/

// 백준 제출용
//const readFileSyncAddress = '/dev/stdin';

// VSC 테스트용
const readFileSyncAddress = 'input.txt';

let fs = require('fs');
let input = fs.readFileSync(readFileSyncAddress).toString().split('\n');
let newArr = [];

const testCaseNum = +input[0];

for(let i = 1; i<=testCaseNum;i++) {
    const arr=input.map((v)=>+v);
    newArr.push(arr[i]);
}

////////************////////
let result = '';

function DFS(n,sum) {
    let cnt = 0; 
    
    //sum이 n을 초과하는 경우 정답이 아니므로 0을 반환.
    if(sum > n) return 0; 
    
    //sum 이 n이 되면 정답이 되므로 1을 반환.
    if(sum===n){
        return 1;
    }

    //재귀로 반환 받는 숫자만큼 cnt에 누적하며 재귀호출
    else{
        for(let i = 1; i <= 3; i++){
            cnt += DFS(n,sum+i);
        }
    }
    return cnt;
}

for( let i = 0; i < testCaseNum; i++){
    let n = newArr[i];
    result += `${DFS(n,0)}\n`;
}

//제출
console.log(result);