[Python] 색상환 (백준 2482번)

📜 문제

 

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

 

---

🔍 문제 풀이 과정

 

일단 규칙성을 찾아보기 위해 n=4부터 7, k=1부터 4까지의 값을 손으로 계산해 보았습니다.

 

 

풀면서 찾게 된 점화식은 다음과 같습니다.

dp[n][k] = dp[n-2][k-1] + dp[n-1][k]

예를 들어, 각 색상을 1번부터 n번까지의 번호라고 가정하고 1번과 n번이 연결되었다고 해보겠습니다.

n=7, k=3 인 상황에서 가능한 경우는 다음과 같습니다.

1 3 6
1 4 6
2 4 7
2 5 7
3 5 7

1 3 5
2 4 6

위의 경우를 잘 살펴보면 n=5, k=2일 때 가능한 값에

6과 7이 추가된 경우의 수가 있고

1 3  +  6
1 4  +  6
2 4  +  7
2 5  +  7
3 5  +  7

n=6, n=3일때 가능한 값도 존재합니다.

1 3 5
2 4 6

 

 

n=6, k=2 인 상황에서 가능한 경우도 살펴보면

1 5
2 6
3 6
4 6

1 3
1 4
2 4
2 5
3 5

n=4, k=1인 상황에서 가능한 경우에 5,6이 붙은 경우나

1  +  5
2  +  6
3  +  6
4  +  6

n=5, k=2인 상황에서 가능한 배치가 있습니다.

1 3
1 4
2 4
2 5
3 5

같은 방법으로 계속 계산해 보면 n=n, k=k인 경우는

• n=n-2, k=k-1 일 때 가능한 경우에 n 또는 n-1 색상을 추가한 경우
  • = dp[n-2][k-1]
• n=n-1, k=k 일 때 가능한 경우
  • = dp[n-1][k]

2가지 경우의 수 의 합으로 나타낼 수 있다는 것을 알 수 있습니다.

n=4부터 주어지므로, dp 테이블에서 필요한 n=2,3의 값만 먼저 초기화 해주고 아래와 같이 풀었습니다.

import sys

input = sys.stdin.readline

n = int(input())
k = int(input())

dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

dp[2][0] = 1
dp[2][1] = 2

dp[3][0] = 1
dp[3][1] = 3

for i in range(4, n + 1):
    for j in range(k + 1):
        dp[i][j] = dp[i - 2][j - 1] + dp[i - 1][j]

print(dp[n][k] % 1000000003)

 

---

📜 결과