CLASS 3 ESSENTIAL
주어진 자연수를 1, 2, 3의 합으로 나타내는 경우의 수를 구하는 문제입니다. 문제에 구체적으로 적혀있지는 않지만 수를 더하는 순서 또한 고려해야 합니다. 즉, 4를 나타낼 때 1+3과 3+1은 서로 다른 경우가 됩니다. 이 조건이 붙게 되면 점화식을 쉽게 세울 수 있게 됩니다. 먼저 1을 만드는 경우는 1가지, 2를 만드는 경우는 2가지, 3을 만드는 경우는 4가지가 됨을 직관적으로 구할 수 있습니다. 이제 4 이상의 수에 대해 경우의 수를 구하는 방법은 다음과 같을 것입니다.
\(n(n\le 4)\)을 1, 2, 3의 합으로 나타내는 경우는 ① \(n-3\)을 만드는 경우에 3을 더하는 것, ② \(n-2\)를 만드는 경우에 2를 더하는 것, ③ \(n-1\)을 만드는 경우에 1을 더하는 것의 합이다.
이러한 방법으로 보게 되면 ①, ②, ③의 경우는 모두 겹치는 부분이 없으면서 \(n\)을 1, 2, 3의 합으로 나타내는 모든 경우를 나타내게 됩니다. 이를 점화식으로 나타내면 아래와 같습니다.
\[a_n=a_{n-1}+a_{n-2}+a_{n-3},a_1=1,a_2=2,a_3=4\]위 점화식을 기반으로 입력받은 n에 대해 알맞은 값을 출력하면 됩니다.(사실 이건 Tribonacci Sequence라고 불리는 수열입니다!)
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-12-19 23:55:48 |