9095. [Python]1, 2, 3 더하기

1. 문제

 

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

9095번: 1, 2, 3 더하기

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 512MB
• DP(Dynamic Programming)

 

3. 파이썬 코드

 

# 1 = 1     1                                                        
# 2 = 1+1 2   2
# 3 = 1+1+1, 2+1, 1+2 3  4
# 4 = 1+1+1+1, 3+1, 1+3, 2+2, 1+1+2, 2+1+1, 1+2+1    7
# 5 = 1+1+1+1+1, 3+2, 2+3, 1+1+3, 1+3+1, 3+1+1, 2+2+1 1+2+2, 2+1+2 1+1+1+2, 2+1+1+1, 1+2+1+1, 1+1+2+1  13
# 6 = 1+1+1+1+1+1,3+3, 3+2+1, 2+3+1,1+3+2, 3+1+2 1+2+3, 2+1+3,3+1+1+1, 1+3+1+1, 1+1+3+1, 1+1+1+3, 2+2+2, 2+2+1+1, 2+1+2+1, 2+1+1+2, 1+2+1+2, 1+2+2+1, 1+1+2+2 , 2+1+1+1+1, 1+2+1+1+1, 1+1+2+1+1, 1+1+1+2+1, 1+1+1+1+2 24
# 7 = 44

T = int(input())

for tc in range(T):
    # 1 일때 1, 2일때 2, 3일때 4
    DP = [1, 2, 4]
    N = int(input())
    # i - 3, i - 2, i - 1 값들이 더해진다.
    for i in range(3,N):
        DP.append(DP[i-1]+DP[i-2]+DP[i-3])
    print(DP[N-1])

 

4. 문제를 풀고난 후 생각

 

• 1, 2, 3 값들에서 직접 이전 계산식들에서 +1 혹은 2, 3 값들을 넣어보며 규칙성을 찾았다.
• i 값을 기준으로 -3, -2, -1 값들의 갯수의 합이 다음 값을 결정 짓는 것을 확인했고, 그 규칙에 맞게 값을 추가해 줬다.
• DP(Dynamic Programming) 문제들은 대부분 점화식으로 접근하는 것이 풀기가 쉬웠던 것 같다.

# 1 = 1     1개                                                
# 2 = 1+1 2   2개
# 3 = 1+1+1, 2+1, 1+2 3  4개
# 4 = 1+1+1+1, 3+1, 1+3, 2+2, 1+1+2, 2+1+1, 1+2+1    7개
# 5 = 1+1+1+1+1, 3+2, 2+3, 1+1+3, 1+3+1, 3+1+1, 2+2+1 1+2+2, 2+1+2 1+1+1+2, 2+1+1+1, 1+2+1+1, 1+1+2+1  13개
# 6 = 1+1+1+1+1+1,3+3, 3+2+1, 2+3+1,1+3+2, 3+1+2 1+2+3, 2+1+3,3+1+1+1, 1+3+1+1, 1+1+3+1, 1+1+1+3, 2+2+2, 2+2+1+1, 2+1+2+1, 2+1+1+2, 1+2+1+2, 1+2+2+1, 1+1+2+2 , 2+1+1+1+1, 1+2+1+1+1, 1+1+2+1+1, 1+1+1+2+1, 1+1+1+1+2 24개

 

5. 문제를 푸는데 도움이 되는 지식

 

• DP(Dynamic Programming)