[Python]BAEKJOON 9095번 1,2,3 더하기

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

9095번: 1, 2, 3 더하기

 

동적계획 알고리즘(Dynamic Programming(aka. DP))을 이용해서 푼다. 

배열 d를 만들고, d[1]=1, d[2]=2, d[3]=4로 초기값을 설정한다. 3개나 초기값을 설정한 이유는 이 문제의 점화식이 다음과 같기 때문이다. 

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

 

이 점화식이 유도되는 과정은 아래 예시를 참고. 

i = 4일 때, d[4] = d[3]+d[2]+d[1]

4 = 

(3) + 1	d[3] = 4(개)	(1+1+1)+1	(3)+1	(2+1)+1	(1+2)+1
(2) + 2	d[2] = 2(개)	(1+1)+2	(2)+2
(1) + 3	d[1] = 1(개)	(1)+3

 

Try1 - runtime error 실패

import sys
input = sys.stdin.readline
res = []
for _ in range(int(input())):
    n = int(input())
    d = [0 for i in range(n+1)]
    d[1],d[2],d[3] = 1,2,4 
    for i in range(4,n+1):
        d[i] = d[i-1]+d[i-2]+d[i-3] 
    res.append(d[n])
print(*res,sep='\n')

-> runtime error(type error)가 발생하는 이유는 index error - 즉, n = 1 또는 2일 경우, 런타임 에러가 발생.  d = [0 for i in range(n+1)]에서 range(2) 또는 range(3)이 되어 한줄에 초기화한 d[1],d[2],d[3] = 1,2,4 값들이 출력되지 않을 수 있음. 따라서 d = [0 for i in range(n+1)]와 같이 하지 않고, d=[0]*(max(4, n+1))라고 해주면, 최소 index = 0,1,2,3의 배열은 만들어지게 됨. 

Sol1

import sys
input = sys.stdin.readline
res = []
for _ in range(int(input())):
    n = int(input())
    d = [0]*(max(4, n+1))                   #이 부분만 수정
    d[1],d[2],d[3] = 1,2,4 
    for i in range(4,n+1):                      
        d[i] = d[i-1]+d[i-2]+d[i-3] 
    res.append(d[n])
print(*res,sep='\n')

Sol2

n은 11보다 작다는 조건에 따라 d=[0]*(max(4, n+1))라고 쓸 필요도 없이, d = [0]*11라고 쓰면 그만이다.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    d = [0]*11
    d[1],d[2],d[3] = 1,2,4 
    for i in range(4,11):                            # 범위도 (4,11)로 바꿨다. 
        d[i] = d[i-1]+d[i-2]+d[i-3] 
    print(d[n])

Sol3

T = int(input())
lst = [int(input()) for i in range(T)]
d = [0]*11
d[1],d[2],d[3] = 1,2,4 
for i in range(4,11):
    d[i] = d[i-1]+d[i-2]+d[i-3] 
for n in lst:
    print(d[n])