[백준] 9095번: 1, 2, 3 더하기

✅문제: 9095번

📌문제풀이

1, 2, 3의 합으로 숫자 n을 표현하는 방법의 수를 계산하는 문제임. n은 최대 10까지 주어지며, 이를 동적 계획법(DP)을 사용해 해결함.

1. DP 배열 초기화
   • dp[i]: 숫자 i를 1, 2, 3의 합으로 나타내는 방법의 수를 저장하는 배열
   • 초기값 설정
     • dp[1] = 1dp[1]: 1을 표현하는 방법은 1개 (1)
     • dp[2] = 2dp[2]: 2를 표현하는 방법은 2개 (1+1, 2)
     • dp[3] = 4: 3을 표현하는 방법은 4개 (1+1+1, 1+2, 2+1, 3)
2. 점화식
   • 숫자 i를 1, 2, 3의 합으로 표현하기 위해 고려해야 할 사항
     • 마지막 숫자 1: dp[i−1]
     • 마지막 숫자 2: dp[i−2]
     • 마지막 숫자 3: dp[i−3]
   • 따라서, dp[i]=dp[i−1]+dp[i−2]+dp[i−3]가 유도됨.
3. 결과 출력
   • 주어진 테스트 케이스 t에 대해서 dp[n]을 출력함.

t = int(input())

dp = [0, 1, 2, 4] + [0] * 7

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

for _ in range(t):
    n = int(input())
    print(dp[n])

📌후기

• DP에 대한 기본적인 문제였음. 점화식을 유도하는 과정에서 문제를 이해할 수 있었음.