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

✏️ 문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

🤖 입출력 예시

 

💡풀이

이것도 아주 유명한 DP 문제다. dp[1]~dp[5]의 값과 그 값이 나오는 조합을 직접 적어보니까 규칙이 보였는데, DP 유형으로 추정되는 문제를 해결하기 위해 항상 손으로 다 적어볼 수는 없는 법..! 좀 더 논리적인 접근을 위해 챗지피티의 도움을 받았다.

 

일단 결론부터 말하면 이 문제의 점화식은 `dp[i] = dp[i-1]+dp[i-2]+dp[i-3]`으로 정의할 수 있다.

 

1) 예시

 dp[i-1]은 i-1에 1을 더하는 방법, dp[i-2]는 i-2에 2를 더하는 방법, dp[i-3]은 i-3에 3을 더하는 방법이다. 이제 `i=5`로 가정하고 이후 설명을 작성해보겠다.

 

① dp[4]

dp[4]는 숫자 4를 1, 2, 3의 합으로 만드는 방법의 수를 의미하는데 이 때의 모든 결과에 1을 더하면 그 값들이 dp[5]의 일부가 된다.

 

 

어 그림이 너무 크다 ㅠ

 

② dp[3]

위와 동일하게 dp[3]을 구성하는 모든 값들에 2를 더하면 그 값이 dp[5]의 일부가 된다. `1+1+1`이 dp[3]의 일부인데 여기에 2를 더한 `1+1+1+2`는 5가 되는 것!

 

2) 코드

T = int(input())

dp = [0]*11

dp[1], dp[2], dp[3] = 1, 2, 4

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])

 

이 문제는 조금만 더 붙잡고 있었다면 내 힘으로 풀었을 것 같은데 성급했다는 생각이 든다. 스스로 생각하는 힘을 기르자