[BOJ] 2482 색상환 (Python3)

문제

색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다.

색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다. 시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다.

주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보자. 먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 있게 10개의 색을 선택하는 경우의 수는 2이지만, 시각적 대비 효과를 얻을 수 있게 11개 이상의 색을 선택할 수 없으므로 이 경우의 수는 0이다.

주어진 정수 N과 K에 대하여, N개의 색으로 구성되어 있는 색상환 (N색상환)에서 어떤 인접한 두 색도 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 프로그램을 작성하시오.

입력

입력 파일의 첫째 줄에 색상환에 포함된 색의 개수를 나타내는 양의 정수 N(4 ≤ N ≤ 1,000)이 주어지고, 둘째 줄에 N색상환에서 선택할 색의 개수 K(1 ≤ K ≤ N)가 주어진다.

출력

첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다.

정답 코드

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

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

for i in range(n + 1):
    dp[i][0] = 1
    dp[i][1] = i
    
for i in range(2, n + 1):
    for j in range(2, k + 1):
        dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % 1000000003
        
answer = (dp[n-3][k-1] + dp[n-1][k]) % 1000000003
print(answer)

문제 풀이

그냥 대략 조합이나 순열을 구해야 하는데 경우의 수가 무조건 시간초과가 나거나 결과 값을 뭐로 나누라 한다? -> DP라고 생각하면 된다.

DP는 큰 문제를 작게 쪼개서 이전결과를 기반으로 다음결과를 내는 알고리즘이니, 문제를 보자마자 나온 n과 k를 이용해서 이차원배열을 만들고 이를 기록해나가야한다.

따라서 DP 배열을 선언해주고,n개의 색에서 k개를 뽑아야하는 경우의수를 dp[n][k]라고 생각하기로 하자.

그럼 아예 빈 배열로 DP를 사용할 수는 없으니 초기 배열은 조금 채워줘야한다.

n개에서 0개를 고르는 경우의 수는 모두 한가지일 것이다. 그럼 n개에서 1개를 고르는 경우는? n개일 것 이다. 그럼 n개에서 3개를 고르는 경우는? 여기부터는 손으로 구해볼수는 있지만 직관적으로 구해질 정도로 간단하지는 않으므로 DP를 이용해준다.

DP는 이전 값을 통해 다음값을 도출하는 것이기 때문에, n이나 k가 늘어났을 때의 경우를 그 이전의 경우를 통해서 생각해야한다.

n이 2개인 경우까지 생각했으니, 이를 기반으로 n이 3인 경우를 생각해보자.

n이 2개인 경우에서 2개를 고르는 경우의 수는 2였다.

이 상태에서 n이 3이되어 3개의 색에서 2개를 고르는 경우라면? 기존 경우의 수에서 두가지의 경우의 수가 더 추가된다.

1. 새로 추가된 색을 포함하는 경우
2. 그렇지 않은경우

1번의 경우는 3번째로 추가된 색을 포함하는 경우기 때문에, 2번째로 추가된 색이 안칠해져있으며, 현재 하나를 더 칠할 수 있도록 현재 칠한 색의 수가 1이어야한다.따라서 한가지 색중에 하나를 칠한 경우의수와 같다. dp[n - 2][k - 1]이다.

2번의 경우는 색을 칠하지 않기 때문에, 2가지 색중에서 2가지를 이미 칠한 경우의수와 같다. 따라서 dp[n - 1][k] 이다.

따라서 dp[n][k] = dp[n-2][k-1] + dp[n-1][k]로, 이전의 결과값들로 다음값을 정할 수 있게 된다.