★파이썬(Python) 코테 대비 DP : 백준 9095 1, 2, 3 더하기

[시작 체크 리스트]

1. 1시간 지났으나 발상 불가 또는 아예 다른 길
2. 코드 50% 정도 완성
3. 1시간 보다 더 걸려서 코드 완성
4. 코드는 다 돌아가는데 효율성에서 걸림
5. 코드 완성

[완료 후 체크 리스트]

1. 아예 모르겠음
2. 중간 정도 이해함
3. 완벽히 이해함

[첨언]

점화식 도출이 아래 처럼 된다는 건 알겠는데, 이렇게 귀납적으로 깨달아야만 하는 부분인지, 특별히 찾는 팁이 있는 건지 모르겠음

[구글링이후]

1.발상

점화식 : dp[n] = dp[n-1]+dp[n-2]+dp[n-3]

dp	방법	분석	총계
dp[1]	1		1개
dp[2]	2		2개
	1+1
dp[3]	3		4개
	1+2 2+1 1+1+1	dp[2]에 1 더해주기
dp[4]	1+3 3+1 1+2+1 2+1+1 1+1+1+1	dp[3]에 1 더해주기	7개
	2+2 1+1+2	dp[2]에 2 더해주기
dp[5]	1+3+1 3+1+1 1+2+1+1 2+1+1+1 1+1+1+1+1 2+2+1 1+1+2	dp[4]에 1 더해주기	13개
	3+2 1+2+2 2+1+2 1+1+1+2	dp[3]에 2 더해주기
	2+3 1+1+3	dp[2]에 3 더해주기

2.작성 코드

test_case=int(input())

input_list=[]
for i in range(test_case):
    input_list.append(int(input()))
dp=[1,2,4]

for i in range(3,max(input_list)):
    dp.append(dp[i-1]+dp[i-2]+dp[i-3])

for i in input_list:
    print(dp[i-1])

(출처 : https://www.acmicpc.net/problem/9095)