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

문제

15992번: 1, 2, 3 더하기 7

[ 문제 조건 ]

• 정수 n을 가지고 m개의 수를 사용해야 함.
• 즉, 4를 가지고 2개의 수를 사용한다면 (2+2), (1+3), (3+1) 총 3개의 경우의 수가 있을 것이다.

[ 해결순서 ]

1. dp 문제는 늘 전에 계산한 값들을 다시 이용해서 사용해야 하므로 고정된 범위의 1~3의 값을 미리 계산해서 dp 배열에 넣었다.
2. 그리고, 첫번째 시도 풀이에서 메소드를 넣어 값을 구하려고 했는데 이렇게 하면 시간초과가 발생한다.
3. ❗️ 여기서 중요하고 내가 간과한 사실을 알아냈는데, 메소드로 반복해서 값을 구하면서 dp 배열을 계산하면 테스트 케이스만큼 dp 배열의 값을 계산하게 된다. 한번 구해서 갱신한 dp 배열은 공유해서 사용하기 때문에 굳이 테스트 케이스마다 중복해서 계산할 필요가 없다. 시간낭비이다. 백준에 1차시도 코드를 제출해도 시간초과로 "실패"로 뜬다.
4. 그래서 dp 배열의 길이를 1001로 해도 정답은 뜨지만, 메모리 덜 차지하게 하기위해 모든 케이스의 n의 값 중 큰 값을 구한 다음에 그 값만큼 dp 배열을 생성해서 계산하면 된다.
5. 중첩 for문으로 먼저 dp 배열의 값을 구한다음에 (1번만) 입력받은 조건의 dp 배열의 값을 출력해주면 된다.

[ 점화식 ]

dp[k][x] = (dp[k-3][x-1] + dp[k-2][x-1] + dp[k-1][x-1]) % 1000000009

✏️한줄평

: dp는 정말 해도해도 뭔가 어렵다. 점화식 짜기가 힘들다ㅠㅠ 많이 풀는 것만이 답이겠지.. dp를 잘 풀고 싶다..

---

코드

1차 실패코드

def solve(n, m): # 4,2
    for k in range(4, n+1): # 5
        # dp[k][1] = 0
        for x in range(1, k): # 5
            if x!=1:
                dp[k][x] = dp[k-3][x-1] + dp[k-2][x-1] + dp[k-1][x-1]%1000000009

            if k==n and x==m:
                print(dp[k][x])
                
t = int(input())
dp = [[0] * 1001  for _ in range(10)]
dp[1][1] = 1
dp[2][1] = 1
dp[2][2] = 1
dp[3][1] = 1
dp[3][2] = 2
dp[3][3] = 1
     

for _ in range(t):
    n, m = map(int,input().split())
    if n <= 3 and m <= n:
        print(dp[n][m])
    else: 
        solve(n,m)
    # print(dp)