[백준] 9095 1,2,3 더하기 (파이썬 Python)

[백준] 9095 1,2,3 더하기 (파이썬 Python)

https://www.acmicpc.net/problem/9095

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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

---

풀이 과정

• 나의 풀이

① 이 문제에서 직관적으로 파악한 것은 '정수 n을 숫자 1,2,3을 이용해 1,2,3의로만 이루어진 숫자합을 구성해야하는거구나'이다.

② 아이디어 열기

 DP문제임을 깨닫고 과정 혹은 결과에 의한 규칙을 통한 점화식을 도출하고자하였다.

 n = 1 ; 1

 n = 2 ; 2

 n = 3 ; 4

 n = 4 ; 7

 n = 5 ; 13

 n = 6 ; 24

...

 결과에 의해서는 도무지 이해가 안됬다.

 그러나 과정에 집중해보았다...!!!

 n = 4 인경우 

 4 = 1 + 3   ----- (1)

   = 2 + 2    ----- (2)

   = 3 + 1    ----- (3)

 로 표현 가능하고  (1)의 경우 n=3인 경우의 수와 같고, (2)의 경우 n=2인 경우의 수와 같고 (3)의 경우 n=1인 경우의 수와 같다. 그러므로 1,2,3으로 표현되므로 총 3가지 경우로 나눠서 고려해야했었던 것이었다.

  점화식으로 나타내면 다음과 같다.

  f(n) = f(n-1) + f(n-2) + f(n-3) (n>=4) f(1)=1,f(2)=2,f(3)=4

  이를 실제 코드로 구현하면 다음과 같다.

# 9095
T = int(input())

for i in range(T) :
    n = int(input())
    dp = [0]*(n+1)
    if n == 1 :
        print(1)
    elif n == 2 :
        print(2)
    elif n == 3 :
        print(4)
    else :
        dp[1] = 1
        dp[2] = 2
        dp[3] = 4
        for j in range(4,n+1) :
            dp[j] = dp[j-1] + dp[j-2] + dp[j-3]
        print(dp[n])

---

후기

 과정에서 규칙 찾기가 엄청 힘들었던 문제이다. 왜 굳이 1,2,3으로 표현하라고 했을까?를 생각해보며 1,2,3을 기준으로 더해지는 숫자와 그 숫자가 이미 전에 구한 경우의 수임을 알면 해결하기 쉬웠을 것이다.