[ 2482 ] [ DP ] 색상환

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

2482번: 색상환

 

풀이 과정

---

1. 전체적인 점화식은 다음과 같다. 
   • dp[i][j] = dp[i-1][j] + dp[i-2][j-1]
   • dp[i][j]는 j번 칠했을 때 i번 위치에서의 경우의 수이다.
   • 설명하자면, dp[i-1][j]->dp[i][j]는 i에서 칠하지 않는 경우의 수이고 dp[i-2][j-1]은 i에서 칠하는 경우의 수이다.
2. DP를 두번 진행한다. 한번은 맨 첫번째 색상환을 칠하는 경우, 다른 한번은 첫번째 색상환을 칠하지 않는 경우이다. 이 때 주의해야 할 점은 첫번째 색상환을 칠하는 여부에 따라 dp 테이블 초기화 방식이 다르다는 점이다. 이 점 때문에 시간 많이 잡아먹음..ㅋㅋ
3. 맨 첫번째 색상환을 칠하는 경우에는 마지막 색상환을 칠해선 안되므로 dp[N-1][K]
4. 맨 첫번째 색상환을 칠하지 않는 경우는 마지막 색상환을 칠할 수 있으므로 dp[N][K]
5. 두 합을 구해서 출력시켜준다.

---

소스 코드

---

 

import sys

input = lambda: sys.stdin.readline().rstrip()

N = int(input())
K = int(input())

answer = 0
selected = True

div = 1000000003
for i in range(2):
    dp = [[0] * (K+1) for _ in range(N+1)]
    for i in range(1, N+1):
        if not selected:
            dp[i][1] = i-1
            dp[i][0] = 1
        else:
            dp[i][1] = 1
            dp[i][0] = 0

    for i in range(2, N+1):
        for j in range(2, K+1):
            dp[i][j] += dp[i-1][j]
            if i >= 2 and j >= 1:
                dp[i][j] += dp[i-2][j-1]

            dp[i][j] %= div

    if selected:
        answer += dp[N-1][K]
    else:
        answer += dp[N][K]
        
    answer %= div
    selected = not selected
    
print(answer)