[백준/Python] #9095 : 1, 2, 3 더하기 - 다이나믹 프로그래밍

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

9095번: 1, 2, 3 더하기

 

아무것도 안보면서 푸는 동안

너ㅓㅓ무 어려웠다...

다이나믹 프로그래밍 너무 어렵다ㅠㅠ 솔직히 말하면 교재에 있는 예제들도 완전 100프로 이해가는건 아님...

그래도 이렇게라도 풀다보면(아직까진 푸는게 푸는게 아닌 단계이지만,,) 조금씩이라도 발전하겠지ㅠ! 

 

머리가 터질 것 같아서 결국 언제나처럼 구글링의 힘을... 빌림 (ㅠ나약한 나ㅠ)

블로그 두 개정도만 참고해도 원리를 대충 알게 됨..

알고리즘의 흐름? 작동 원리랄까? 그 과정이 잘 납득되지가 않는 거같음 이 파트는

 

---

정말 창피하지만 지금까지의 나

부끄러우니 자세히 보지 말아주세요..

요러고 있었음;; 하ㅋㅋㅋㅋ

 

.

.

.

 

결론은

d = [0] * 11    # 어차피 수도 작으니 n + 1 대신 그냥 11로 해주고

d[0] = 0
d[1] = 1
d[2] = 2    # 1+1, 2
d[3] = 4    # 1+1+1, 1+2, 2+1, 3

for i in range(4, 11):  # n은 11보다 작다고 했기 때문
    d[i] = d[i - 3] + d[i - 2] + d[i - 1]

T = int(input())
for _ in range(T):
    n = int(input())
    print(d[n])     # for문 두 번 쓸 필요 없이 여기서 출력까지 한 번에 처리해줌

이렇게 풀면 간단히 풀린다

 

---

참고:

https://e-you.tistory.com/304

[Python] 백준 #9095 - 1, 2, 3 더하기

https://yongku.tistory.com/1273

백준 9095번 1, 2, 3 더하기 파이썬(Python)