예시 5: 1개~3개씩 물건 옮기기 경우의 수

📖 학습 내용

문제 설명

N개의 물건을 한 번에 1개, 2개, 3개씩 옮길 수 있을 때 모든 운반 방법의 수를 구합니다.

입력 형식

옮겨야 할 물건 수 N을 입력합니다.

출력 형식

가능한 운반 방법의 수를 출력합니다.

학습 내용

Scoring note: 작은 N부터 점화식을 세워 누적하면 효율적으로 해결할 수 있습니다.

📥 테스트 입력값

🔎 실행 결과

💡 힌트 코치

점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 입니다.

✅ 정답 공개

n = int(input())
if n == 1:
    print(1)
elif n == 2:
    print(2)
elif n == 3:
    print(4)
else:
    dp = [0] * (n + 1)
    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])