15989 1,2,3 더하기 4

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

#dp

15989번: 1, 2, 3 더하기 4

#15989 1,2,3 더하기 4

 

#1

import sys
input=sys.stdin.readline
#스탠다드 인풋

t=int(input())
#테스트 케이스 t 입력

num=[]
for n in range(t):
    num.append(int(input()))
#num 입력

dp=[[],[1,0,0],[1,1,0],[1,1,1]]
#인덱스 i 의 인덱스는 순서대로 1만 사용한 경우 2만 사용한 경우 3만 사용한 경우 이다.

for i in range(4,max(num)+1):
    next=[]
    next.append(dp[i-1][0])
    next.append(dp[i-2][1]+dp[i-2][0])
    next.append(dp[i-3][2]+dp[i-3][1]+dp[i-3][0])
#인덱스 i 는 i-1 에서 1만 사용한 수 ~ 이런식이다.

    dp.append(next)
#답

 

#코드를 찾던 중 다른 코드가 있어서 생각하게 됐다.

 

#2

 

import sys
input = sys.stdin.readline

t = int(input())
l = []

for _ in range(t):
    l.append(int(input()))

dp=[1 for i in range(max(l)+1)]

for i in range(2, max(l)+1):
    dp[i] += dp[i - 2]

for i in range(3, max(l)+1):
    dp[i] += dp[i - 3]

for i in l:
    print(dp[i])

 

# 이것 역시 잘 생각을 해보니 i-2 i-3 가 들어있는 for문의 순서가 중요했다. 이유인 즉슨 i-2 for문 부터 시작해야 1만 사용하는 수부터 저장이 되어 결국에는 이전에 내가 사용했던 코드의 알고리즘처럼 작동이 되었다.

 

#점화식을 시작할때 생각해야할 점은 내가 이미 사용하고 있는 방법, 즉 인간의 뇌로 이미 당연하게 사용하고 있는 것을 컴퓨팅적 사고로 풀어낸다라고 명심하는 것이다. 이 문제같은 경우에도 경우의 수를 생각할때 이미 나는 답을 알고 있었다. 2를 제외하고 생각하면 i-2를 2이하의 수로 고르는 것이다. 같은 생각을 하면서 풀었는데 결국에는 그것을 컴퓨터로 표출하지 못해서 굉장히 시간이 많이 걸렸던 문제, 점화식에 관한 문제를 좀더 풀어봐야겠다.