백준 15990번 파이썬 문제풀이(DP - 1,2,3 더하기 5) - 자세한 설명

 

---

11052번 문제하고 거의 동일한 문제이지만 11052와 비슷한 단순한 DP문제라고 생각하고 풀었기에 아무리 생각해도 답이 나오지 않아 이 문제를 풀지 못했다. 이러한 문제 유형의 핵심은 이것이다. N이 만약에 6이라고 생각하자. 그렇다면 N이 3일때 나올 수 있는 경우의 수(1+2,2+1,3)를 쭉 적어놓고 여기에+3만 해주면 6이 된다. 이와 마찬가지로 N이 4일때 나올 수 있는 횟수, N이 5일때 나올 수 있는 횟수 다 동일하게 적용이 된다.  이런식으로 점화식을 세워 쭉쭉 구해나가면 되는 것이다. 

 

그렇다면 나올 수 있는 점화식이 이것이다.

dp = [[0 for _ in range(3)] for _ in range(11)] #dp초기화

# 각각 1,2,3으로 끝나는 경우의 수
dp[1] = [1, 0, 0]
dp[2] = [1, 1, 0]
dp[3] = [2, 1, 1]

for i in range(4, 11):
    # 만약 i가 6일때

    # 5에서 1,2,3으로 끝난 경우들에 1을 더해주면 6이다.
    dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i-1][2]
    # 4에서 1,2,3으로 끝난 경우들에 2를 더해주면 6이다.
    dp[i][1] = dp[i - 2][0] + dp[i - 2][1] + dp[i-2][2]
    # 3에서 1,2,3으로 경우 들에 3을 더해주면 6이다.
    dp[i][2] = dp[i - 3][0] + dp[i - 3][1] + dp[i-3][2]
    
    #N이 6일때의 횟수
    print(sum(dp[6])

-> 위의 점화식을 다시 정리하자면 11052문제처럼 dp[i] = dp[i-3] + dp[i-2] + dp[i-1]이 된다.

 

그렇다면 15990은 위를 약간만 변형하면된다. 예를들어 5에서 끝이 1,2,3으로 끝난 경우들에서 1을 더해주면 6인데 위 문제에서는 같은 숫자가 연속으로 나올 수 없다. 따라서 5일때 1로 끝난 경우만 무시해주면 된다. 따라서 바뀐 점화식은 다음과 같이 나온다.

dp = [[0 for _ in range(3)] for _ in range(100001)]

# N이 1일때 2일때 3일때 각각 1,2,3으로 끝나는 경우의 수 미리 초기화
dp[1] = [1, 0, 0]
dp[2] = [0, 1, 0]
dp[3] = [1, 1, 1]

for i in range(4, 100001):
    # 만약 i가 6이라면
    
    # 5에서 2와 3으로 끝난 횟수에 1을 더하면 6이므로 그 두개의 횟수를 더해주어 대입.
    dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) 
    # 4에서 1과 3으로 끝난거에 2를 더하면 6이므로 그 두개의 횟수를 더해주어 대입.
    dp[i][1] = (dp[i - 2][0] + dp[i - 2][2]) 
    # 3에서 1과 2로 끝난거에 3을 더하면 6이므로 그 두개의 횟수에 더해주어 대입.
    dp[i][2] = (dp[i - 3][0] + dp[i - 3][1])

 

따라서 위의 점화식만 잘 이해 하였다면 쉽게 풀 수 있는 문제이다.

문제의 정답 코드는 다음과 같다.

import sys

input = sys.stdin.readline

dp = [[0 for _ in range(3)] for _ in range(100001)]

# N이 1일때 2일때 3일때 각각 1,2,3으로 끝나는 상황의 개수 미리 초기화
dp[1] = [1, 0, 0]
dp[2] = [0, 1, 0]
dp[3] = [1, 1, 1]

for i in range(4, 100001):
    # 만약 i가 6이라면
    
    # 5에서 2와 3으로 끝난 횟수에 1을 더하면 6이므로 그 두개의 횟수를 더해주어 대입.
    dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % 1000000009
    # 4에서 1과 3으로 끝난거에 2를 더하면 6이므로 그 두개의 횟수를 더해주어 대입.
    dp[i][1] = (dp[i - 2][0] + dp[i - 2][2]) % 1000000009
    # 3에서 1과 2로 끝난거에 3을 더하면 6이므로 그 두개의 횟수에 더해주어 대입.
    dp[i][2] = (dp[i - 3][0] + dp[i - 3][1]) % 1000000009

T = int(input())
for i in range(T):
    n = int(input())
    print(sum(dp[n]) % 1000000009)

-> 여기서 문제의 요구에따라 1000000009로 나눈 나머지를 출력하는데 이해가 안되는 부분이 계산에서 한번 나누고 출력에서 또 한번 1000000009로 총 2번을 나눈 나머지를 출력한다는 것이다.

 

*혹시 이부분 설명이 가능하다면 댓글남겨주시면 정말 감사하겠습니다^_^!!