💡문제

백준 9095번 문제 링크

🍀풀이

dp를 풀기 위해서는 1. 테이블 정의, 2. 점화식 찾기 의 과정을 거쳐야 한다.
여기서의 테이블 정의는 n을 1,2,3의 합으로 나타내는 방법의 수?이고
점화식은 문제에 있는 예시를 통해 찾아냈다.

정수 4를 1,2,3의 합으로 나타내는 방법이 나와있는데
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
이렇게 7가지이다.

dp를 풀어봤을 때 꼭 뭔가 규칙이 있어서 중복을 없애기 위해 이전의 값으로 조합해서 찾아보니까

1+1+1+1, 1+2+1, 2+1+1, 3+1
1+1+2, 2+2
1+3

이렇게 해서 D[3]+D[2]+D[1] 인것을 알았다!
그래서 이 값들로 초기값을 만들고 4부터 반복문을 돌렸다.

틀린코드

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n = int(input())
    D = [0] * (n+1)
    D[1] = 1
    D[2] = 2
    D[3] = 4
    for i in range(4, n+1):
        D[i] = D[i-1] + D[i-2] + D[i-3]
    print(D[n])

이렇게 작성을 해서 테스트 케이스 실행 했을때는 맞았는데 제출을 하니까 런타임 에러가 나왔다.
이유는 현재 초기값을 D[3]까지 주고 있는데 n이 만약 3미만이라면? 인덱스 에러가 발생한다.

정답코드

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n = int(input())
    D = [0] * (max(4, n+1))
    D[1] = 1
    D[2] = 2
    D[3] = 4
    for i in range(4, n+1):
        D[i] = D[i-1] + D[i-2] + D[i-3]
    print(D[n])

그래서 (max(4, n+1)) 이렇게 해서 최대 4개가 생성되도록 수정을 하였다!