[백준/DP]9095

841 단어 백준DPDP

9095번 문제
DP는 메모이제이션을 사용해야한다고 한다

def solution(n):

    count_array = [0 for _ in range(n+1)]
    count_array[0] = 1

    for i in range(n+2):

        if i+1 <= n:
            count_array[i+1] += count_array[i]
        if i+2 <= n:
            count_array[i+2] += count_array[i]
        if i+3 <= n:
            count_array[i+3] += count_array[i]     
        
    return count_array[n]

n = int(input())
answer = []
for i in range(n):
    answer.append(int(input()))

for num in answer:
    print(solution(num))

  • 배열에는 지금 index까지 더하는 방식의 갯수를 저장한다
  • 지금 index +1, +2, +3의 위치의 값에는 지금의 index를 미리 더해준다

좋은 웹페이지 즐겨찾기