[백준/Python] 9095번: 1, 2, 3 더하기

문제

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

9095번: 1, 2, 3 더하기

---

문제 요약

정수 n을 입력 받고, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

(1 ≤ n ≤ 10)

 

ex) 정수 4를 1, 2, 3의 합으로 나타내는 방법

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

2 + 1 + 1

2 + 2

1 + 3

3 + 1

---

코드

T = int(input())

dp =[0] * (11)
    # dp[i]는 정수 i까지 1, 2, 3으로 나타낼 수 있는 방법의 수

dp[1] = 1 # 1
dp[2] = 2 # 1 + 1, 2
dp[3] = 4 # 1 + 1 + 1, 1 + 2, 2 + 1, 3

for i in range(4, 11):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

for _ in range(T):
    n = int(input())
    print(dp[n])

---

코드 설명

정수 i를 1, 2, 3으로 나타내는 방법의 수는 정수 i - 1, i - 2, i - 3을 1, 2, 3으로 나타낸 방법의 수를 더한 값과 같다.

 

4를 i라고 했을 때, i - 1, i - 2, i - 3은 각각 3, 2, 1이다.

 

3을 1, 2, 3으로 나타낸 방법은

1 + 1 + 1

1 + 2

2 + 1

3

이다.

 

3을 1, 2, 3으로 나타낸 방법에 1을 더하면 4를 1, 2, 3으로 나타낸 방법이다.

1 + 1 + 1 + 1

1 + 2 + 1

2 + 1 + 1

3 + 1

 

같은 방법으로

 

2를 1, 2, 3으로 나타낸 방법은

1 + 1

2

이다.

 

2를 1, 2, 3으로 나타낸 방법에 2을 더하면 4를 1, 2, 3으로 나타낸 방법이다.

1 + 1 + 2

2 + 2

 

마지막으로

 

1을 1, 2, 3으로 나타낸 방법은

1

이다.

 

1을 1, 2, 3으로 나타낸 방법에 3을 더하면 4를 1, 2, 3으로 나타낸 방법이다.

1 + 3

 

따라서 4를 1, 2, 3으로 나타낼 수 있는 방법은 4가지 + 2가지 + 1가지 총 7가지이다.

 

코드 상으로는 메모이제이션 테이블 dp에 1부터 10까지 1, 2, 3으로 나타낼 수 있는 방법을 미리 저장하고, 입력 받은 정수 n에 해당하는 dp[n]값을 출력한다.