[node.js,백준]15988 - 1,2,3 더하기 3

목차

 문제

링크

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

문제

정수 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은 양수이며 1,000,000보다 작거나 같다.

 

출력

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

 

주저리

이전 1,2,3더하기 문제는 아래 함수로 해결할수 있었기 때문에 이번에도 아래와 같은 방법으로 풀이하려 하였었다. 하지만 특정 수가 넘어가면 너무 많은 풀이를 시도해서그런지 에러가 발생하였다.

function testF(N) {
    if (N === 0) {
        arrs[0] = 0;
        return 0;
    }
    if (N === 1) {
        arrs[N] = 1;
        return 1;
    }
    else if (N === 2) {
        arrs[N] = 2;
        return 2;
    }
    else if (N === 3) {
        arrs[N] = 4;
        return 4;
    }
    else {
        if (arrs[N]) {
            return arrs[N];
        }
        else {
            arrs[N] = (testF(N - 1) % mod) + (testF(N - 2) % mod) + (testF(N - 3) % mod)
            return arrs[N]
        }

    }
}

위는 에러 코드입니다.

그래서 아래와 같은 새로운 해결방법이 필요하여서 바꾸었다.

문제에선 여러개의 값을 주는데(rest에 할당) 그중 최대값을 찾아서 그만큼 미리 메모제이션을 해두고 값을 가져오기만 하는 방식으로 변경하였다.

 

풀이

 입력 처리

• 각 줄에 하나씩 입력받은 정수를 처리합니다. 첫 번째 줄은 테스트 케이스의 수 T를 나타냅니다. 이후의 줄들은 각 테스트 케이스에 해당하는 정수 n이 주어집니다.

 

 동적 프로그래밍 배열 초기화

• 배열을 초기화하여 n=1일 때 1가지, n=2일 때 2가지, n=3일 때 4가지 방법이 있음을 미리 설정합니다.

 

 점화식 설정

• 각 숫자 n에 대해, n을 만들 수 있는 방법의 수는 `arrs[n-1]`, `arrs[n-2]`, `arrs[n-3]`의 합입니다. 이는 n-1, n-2, n-3에서 각각 1, 2, 3을 더한 값이 n이 되기 때문입니다.

 

 모듈러 연산 적용

• 주어진 문제에서 결과값은 큰 수가 될 수 있으므로, 모든 계산은 주어진 모듈러 값 1000000009로 나눈 나머지를 사용합니다.

 

 결과 출력

• 각 테스트 케이스에 대해 계산된 결과를 출력합니다. n=0인 경우는 0가지 방법이 있으므로 0을 출력합니다.

 코드

// 1,2,3 더하기 3

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString();
let mod = 1000000009
let real = input.trim().split("\n");
let arrs = [0, 1, 2, 4];

function solution(real) {
    let [T, ...rest] = real;
    let returns = [];
    rest = rest.map(Number);
    let maxes = Math.max(...rest)
    for (let j = 4; j <= maxes; j++) {
        arrs[j] = (arrs[j - 1] + arrs[j - 2] + arrs[j - 3]) % mod;
    }
    for (let row of rest) {
        row = Number(row);
        if (row === 0) {
            returns.push(0)
        } else {
            returns.push(arrs[row])
        }

    }
    // console.log(arrs)
    console.log(returns.join("\n"));
}
solution(real);