Written by java-style
on 2021-09-25

1,2,3 더하기 5 (15990번) [node.js, JavaScript]

문제 설명

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

Point

같은 수를 두 번 이상 연속해서 사용하면 안 되기 때문에, 우리는 1, 2, 3중 마지막 자리가 어떤 숫자로 끝나는지 알아야 합니다.

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

인덱스 0번은 신경 쓰지 않아도 됩니다. 인덱스 번호와 끝자리 숫자를 맞춰 편의상 추가하였습니다.

알고리즘 설명

n이 1 일 때, 마지막 수가 1이 1개, 2와3은 0개이고 [0,1,0,0], n이 2 일 때 2가 1개, 1과3은 0개 [0,0,1,0], n이 3 일 때 2+1, 1+2, 3이기 때문에 끝자리 숫자 1,2,3 모두 1가지씩 가지므로 [0,1,1,1]로 나타낼 수 있습니다.

n이 4 일 때 1+2+1, 3+1, 1+3로 만들 수 있습니다. 끝자리 숫자를 배열로 나타내면 [0, 2, 0, 1]입니다.

4를 만들면 연속되는 숫자 없이 만들기 위해서 숫자 3에서 1을 더해서 만든다고 했을 때 숫자3 배열에서 1로 끝나지 않는 경우는 2와 3이 1가지씩 있습니다.

이를 점화식으로 나타내면 n=4, dp[n][1] = dp[n-1][2] + dp[n-1][3]됩니다. 여기서 dp[n-1]은 숫자 3 배열을 뜻하고, [1]은 1로 끝나는 경우, [2],[3]은 2와 3으로 끝나는 경우를 뜻합니다.

즉, 점화식을 풀이하면 숫자 4의 1로 끝나는 경우는 숫자 3의 2와 3으로 끝나는 경우의 수 합과 같습니다.

한 번 더 설명하겠습니다. 숫자 2에 2를 더해서 4를 만들게 되면 배열2에서 2를 제외한 1과 3의 경우의 수를 더해줘야 하므로 dp[n][1] = dp[n-2][1] + dp[n-2][3] 식으로 나타낼 수 있습니다. 끝자리가 3일때도 마찬가지입니다.

Code

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("

"); solution(input); function solution(input) { input.shift(); const MOD = 1000000009; const maxNum = Math.max(...input); const dp = [ [ 0, 0, 0, 0 ],[ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 1, 1, 1 ] ]; for (let i = 4; i <= maxNum; i++) { dp[i] = [0, (dp[i - 1][2] + dp[i - 1][3]) % MOD, (dp[i - 2][1] + dp[i - 2][3]) % MOD, (dp[i - 3][2] + dp[i - 3][1]) % MOD ]; } const answer = input.map(ele => dp[ele].reduce((sum, cur) => (sum + cur), 0)% MOD); return answer.map(e=>console.log(e)); }

from http://jinblog123.tistory.com/80 by ccl(A) rewrite - 2021-09-25 02:01:47

Top