[BOJ] 15990번 - 1, 2, 3 더하기 5

---

문제설명

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

15990번: 1, 2, 3 더하기 5

사고과정

• 저번 1,2,3 더하기 문제와 난이도가 매우 달랐던 것 같다.. DP 테이블을 1차원으로 정의하고 어떻게든 규칙을 찾아보려 했지만 실패했다. 
• 핵심 풀이는 2차원으로 DP 테이블을 운영하는 것이었고 또 하나는 다이나믹 프로그래밍의 핵심인 "뒤의 입장에서 생각" 하기 였다.
• 어떤 뒤의 입장이냐.. 바로 1, 2, 3 합으로만 이루어진 것을 찾는 것이므로 특정한 수 n을 1, 2, 3의 합으로 만들 때, 그 연산에 사용된 마지막 피연산자 숫자를 의미한다. 예를 들어, n = 4라고 한다면, 4 = 2 + 1 이 있을 것이다. 그러면 1의 입장에서 생각한다는 것.
• 즉 마지막 숫자가 1, 2, 3 이냐에 따라 2차원 DP 테이블을 참조하면 되는데 필자도 텍스트로만은 이해가 안가서 그림으로 도식화 해보았다.
• 참고로 소스코드를 보면 주어진 데이터 범위가 작지는 않기 때문에 테스트 케이스를 입력 받기 전에 애초에 주어질 입력 데이터 범위 최댓값 기준으로 DP 테이블을 한 번 만들어 놓고 테스트 케이스를 입력받을 때마다 참조하도록 메모리 측면에서 절약하는 점도 기억하자.

DP 테이블 설명

 

위에서 예시 하나만 살펴보자. 우선 빨간색 글씨에서 $dp[4][1]$은 4를 1, 2, 3의 합으로 만들 때, 마지막에 1을 사용한 경우의 수를 의미한다. 따라서 $dp[4][1]$은 $dp[3][2]$ 즉, 3을 만들 때 마지막에 2를 사용한 경우의 수와 $dp[3][3]$인 3을 만들 때 마지막에 3을 사용한 경우의 수를 더해준다. 왜 3을 참조하냐고 의구심을 갖는다면 4를 만들 때 마지막에 1을 사용했다는 것은 결국 4 - 1 인 3을 만드는 경우의 수를 참조해야 하는 것이다. $dp[3][1]$을 참조하지 않는 이유는 구하려는 $dp[4][1]$이 마지막에 1의 연산을 사용했기 때문이다. 즉, $dp[3][1]$ 과 $dp[4][1]$은 마지막 연산자가 1로 동일하기 때문에 문제의 조건인 연속해서 숫자를 사용하지 못한다는 조건에 위배된다.

 따라서 위와 같은 방법으로 4를 만들 때, 마지막에 사용한 숫자 2, 3을 사용한 경우의 수도 구해준다. 그리고 문제에서 요구하는 조건에 따라 1,2,3의 합으로 만들되 연속된 숫자를 2번 이상 사용할 수 없는 것을 만족시키면서 4를 만드는 총 경우의 수는 위 DP 테이블의 4번째 행($i = 4$)을 모두 더해주면 된다!

풀이(스스로 못 푼 풀이)

# DP 테이블을 애초에 먼저 만들어 놓기
max_val = int(1e5)
mod = 1000000009
dp = [[0] * 4 for _ in range(max_val+1)]   # 4인 이유: 1,2,3의 합으로만 구하기 때문!
# 행(i)가 만들 수, 열(j)가 i를 만드는 데 사용한 마지막 숫자
# i = 1, 2, 3일 때, dp 테이블 갱신
dp[1] = [0, 1, 0, 0]
dp[2] = [0, 0, 1, 0]
dp[3] = [0, 1, 1, 1]

for i in range(4, max_val+1):
    dp[i][1] = dp[i-1][2] + dp[i-1][3]
    dp[i][2] = dp[i-2][1] + dp[i-2][3]
    dp[i][3] = dp[i-3][1] + dp[i-3][2]

    dp[i][1] %= mod
    dp[i][2] %= mod
    dp[i][3] %= mod

for tc in range(int(input())):
    n = int(input())
    res = sum(dp[n]) % mod
    print(res)