[Python/코테] 백준 9095 1, 2, 3 더하기

9095 1, 2, 3 더하기

문제 및 조건 설명: https://www.acmicpc.net/problem/9095

알고리즘 설계

💡Idea.

N이 작기 때문에, 10중 for문이나 백트래킹을 사용해서 풀 수 있다.

그러나 같은 조건에서 N이 커지면 dp가 아닌 다른 방법을 사용할 수 없다.

 

🎲Step.

1. 테이블 정의하기

D[i] = i를 1, 2, 3를 1, 2, 3의 합으로 나타내는 방법의 수

 

2. 점화식 찾기

ex) D[4] = ?

① 1+1+1+1 ② 3+1 ③ 2+1+1 ④ 1+2+1  → D[3] + 1
⑤ 1+1+2 ⑥ 2+2  → D[2] + 2
⑦ 1+3  → D[1] + 3

즉, D[4] = D[1] + D[2] + D[3]

D[i] = D[i-1] + D[i-2] + D[i-3]

3. 초기값 정하기

D[i] = D[i-1] + D[i-2] + D[i-3] 이므로 초기값이 최소 3개는 주어져야 한다.

D[1] = 1
D[2] = 2
D[3] = 4

알고리즘 구현

✔️n이 클 때도, 매번 d[1] 부터 d[n]을 새로 구하는 것보다 미리 구해두는 것이 효율적이다.

✔️초기값을 어디까지 주고, 어느 범위부터 식을 사용해 계산할 것인지 알아두자.

d = [0] * 20
d[1] = 1
d[2] = 2
d[3] = 4

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

t = int(input())
while t:
    t -= 1
    n = int(input())
    print(d[n])

 

---

출처: 

https://youtu.be/5leTtB3PQu0?si=xxZuJ90OukExoe4C&t=524