[BOJ/9095] 1, 2, 3 더하기

문제

과정

  4라는 숫자를 1, 2, 3을 이용해 표현하면 다음과 같다 하였다.

 

- 1+1+1+1

- 1+1+2

- 1+2+1

- 2+1+1

- 2+2

- 1+3

- 3+1

 

위 케이스를 잘 째려보다 보면 이런 생각이 든다.

 

4라는 숫자는 3에 1을 더해서 만들 수 있고, 2에 2를 더해서 만들 수 있고, 1에 3을 더해서 만들수 있다!

그렇다면 이런 점화식을 얻을 수 있다.

f(n)은 n이라는 숫자를 (1, 2, 3)의 합으로 나타내는 방법의 개수를 뜻하는 함수이다.

f(1) = 1, f(2) = 2, f(3) = 4

n이 만약 3보다 크다면 f(n)은 다음과 같이 정의된다.
f(n) = f(n-1) + f(n-2) + f(n-3)

 어째서 f(n) = f(n-1) + f(n-2) + f(n-3) 일까? f(4)를 잘 봐보자.

 

다음은 3을 (1, 2, 3)의 합으로 나타낸 방법에 1을 더해 새로운 방법으로 4를 표현하는 케이스이다.

- (1 + 1 + 1) + 1

- (1 + 2) + 1

- (2 + 1) + 1

- (3) + 1

 

다음은 2를 (1, 2, 3)의 합으로 나타낸 방법에 2을 더해 새로운 방법으로 4를 표현하는 케이스이다.

- (1 + 1) + 2

- (2) + 2

 

다음은 1을 (1, 2, 3)의 합으로 나타낸 방법에 3을 더해 새로운 방법으로 4를 표현하는 케이스이다.

- (1) + 3

 

이런식으로 숫자 n은 (1, 2, 3)으로 표현할 때, 숫자 n-1, n-2, n-3을 표현하는 방법의 개수 만큼 표현할 수 있다.

결과

정답 코드

def f(n):
    if n > 3:
        return f(n-1) + f(n-2) + f(n-3)
    elif n == 3:
        return 4
    elif n == 2:
        return 2
    else:
        return 1


t = int(input())
for _ in range(t):
    n = int(input())
    print(f(n))