BOJ_9095 : 1, 2, 3 더하기

ㅊ👉 문제링크

9095번: 1, 2, 3 더하기

---

---

🔸 문제 분석 🔸

• 입력받은 수를 1,2,3으로 만들 수 있는 경우의 수를 출력한다.
• dp와 회귀 방법 두 가지로 풀이 가능한데, dp로 풀이했다.
  • 1,2,3 을 만드는 경우의 수는 다음과 같다.
    • (1) : 1  >> 1개
    • (2) : 1+1 , 2  >> 2개
    • (3) : 1+1+1, 1+2, 2+1, 3  >> 4개
  • 1,2,3은 기본값으로 저장해두고, 4부터 '1,2,3 더하기 어떤 수'의 경우의 수를 생각한다.
    • 1+3 : 1 + (3을 표현 할 수 있는 경우의 수)  >> 1+(1+1+1), 1+(1+2), 1+(2+1), 1+(3)
    • 2+2 : 2 + (2를 표현 할 수 있는 경우의 수)  >> 2+(1+1) , 2+(2)
    • 3+1 : 3 + (1을 표현 할 수 있는 경우의 수)  >> 3+(1)
    • 이렇게 모든 조합이 가능한데, 결국 점화식은 dp[n] = dp[n-3] + dp[n-2] + dp[n-1] 이 된다 .

🔸 코드 🔸

dp = [1,2,4]
for _ in range(int(input())):
    t = int(input())
    
    if len(dp) < t:
        for _ in range(t - len(dp)):
            dp.append(dp[-1] + dp[-2] + dp[-3])
    
    print(dp[t-1])

🔸 코드 해석 🔸

• dp 리스트에 1,2,3의 경우의 수 1,2,4를 저장한다.
• 입력받은 수가 dp리스트의 크기보다 크면(존재하지 않는 인덱스면), 차이만큼 반복문을 돌려 리스트를 늘린다.
• dp 리스트에서 입력 수 인덱스의 값을 출력한다.

---

🔸 end 🔸

• 반복 규칙은 눈치챘지만, 원리가 이해되지 않아서 풀이 포스팅을 찾아보았다.
  • 경우의 수가 늘어나는 원리를 간단히 이해할 수 있었다.
• 다른 글에서 회귀로 원리를 설명한 걸 봤는데, 글이 길어질까봐 설명하진 않았다.
  • 0부터 1, 2, 3을 더하고, 각 값에서 다시 1, 2, 3을 더해가며 수가 계속 늘어나는 원리다.
• dp문제를 더 연습해야겠다.