[Python] 백준 15992. 1, 2, 3 더하기 7

문제

정수 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과 m이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 단, 사용한 수의 개수는 m개 이어야 한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n과 m이 주어진다. n은 양수이며 1,000보다 작거나 같다. m도 양수이며, n보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이어야 한다.

---

풀이

도저히 규칙을 찾아내지 못하고... 시험 시간에는 해당 문제를 풀지 못했다... 그렇지만! 따로 문제를 풀기 위해서 풀이를 찾아보다가 풀이 힌트만 얻고 점화식이나 코드 작성은 직접한 문제라서 블로그 글을 작성해본다.

 

https://psh0706.tistory.com/entry/%EB%B0%B1%EC%A4%80-15992-1-2-3-%EB%8D%94%ED%95%98%EA%B8%B0-7-python

백준 15992 1, 2, 3 더하기 7 (python)

일단 힌트를 얻었던 곳은 이곳! 여기서 힌트를 얻어서 문제를 풀 수 있었다. 

 

표를 나타내서 생각을 해보면 보다 쉽게 점화식을 생각해낼 수 있는데...

m이 3일때까지를 계산해보면 이런식으로 표가 만들어지는 걸 확인해볼 수 있다. 표를 잘 들여다보면 규칙이 보이는데...

n-3이고 m-1이면 그곳에 +3을 붙여주면 n,m이고 (주황)

n-2이고 m-1이면 그곳에 +2를 붙여주면 n,m이고 (핑크)

n-1이고 m-1이면 그곳에 +1를 붙여주면 n,m이다! (노랑)

 

이걸 좀 더 확실히 이해하기 위해 DP로 나타내는 방식을 표로 표현해보자.

이런 식으로 dp를 사용할 수 있다는 것을 알게 된다.

그럼 우리가 이걸로 dp코드만 구현해보면..

dp[i][j] = (dp[i-1][j-1] + dp[i-1][j-2] + dp[i-1][j-3])

 

이렇게 나온다는 것을 알 수 있다.

 

 

자!

그래서 이 힌트를 바탕으로 코드를 작성하면....

import sys
input = sys.stdin.readline

t = int(input().strip())

max_n = 1000
max_m = 1000
dp = [[0]*(max_n+1) for _ in range(max_m+1)]
dp[1][1] = 1
dp[1][2] = 1
dp[1][3] = 1
dp[2][2] = 1
for i in range(2, max_m+1):
    for j in range(3, max_n+1):
        dp[i][j] = (dp[i-1][j-1] + dp[i-1][j-2] + dp[i-1][j-3])%1000000009

while t:
    n, m = map(int, input().split())
    print(dp[m][n])
    t-=1

 

 

잘 맞는다는 것을 확인할 수 있다. 첫번째 제출 때 시간초과가 난 것은... n 제한이 1000으로 생각보다 작은 줄 모르고 매 테스트케이스마다 동일한 dp를 만들었고 나머지를 구하는 코드를 넣지 않았었다.

 

그래서 결과적으로 맞은 코드에서는 애초에 n,m을 1000으로 지정해서 모든 값의 dp를 구해놓고 들어오는 n,m값에 맞춰서 출력하도록 코드를 작성하였다. 

 

시간복잡도

시간복잡도는...O(1000000(10의 6승))+O(t)이지 않을까...싶다.