[BaekJoon] 9095 : 1, 2, 3 만들기

3483 단어 백준DPDP

🔦 문제 링크

✍️ 나의 풀이


1, 2, 3을 사용할 수 있으므로 n-1, n-2, n-3의 숫자는 모두 n으로 만들 수 있다.

따라서, 먼저 dp[1], dp[2], dp[3]의 초기 값을 구해준다.
이때 조심해야할 점은 dp크기를 n+3크기로 동적할당해줘야 초기화시 에러가 나지 않는다.

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

🛠 나의 코드


t = int(input())
for _ in range(t):
    n = int(input())
    dp = [0]*(n+3)

    dp[1] = 1
    dp[2] = 2
    dp[3] = 4
    for i in range(4, n+1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

    print(dp[n])

📝 정리


🎈 참고


좋은 웹페이지 즐겨찾기