[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 2482번 _ 색상환

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

2482번: 색상환

[문제]

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

그림 1. 먼셀의 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) 으로 나눈 나머지를 출력한다.

 

[아이디어]

1. 첫번째 색(예시에서는 빨강)을 기준으로 해당 색을 포함할 때와 포함하지 않을 때로 구분하여 생각한다.

2. 첫번째 색을 포함하면, 양 옆 색을 제외한 (n-3)개 중 (k-1)개를 택해야한다. 이때 각각의 색이 인접하지 않기 위해서는 간격이 (k-2)개 필요하다.

3. 첫번째 색을 포함하지 않으면, 해당 색을 제외한 (n-1)개 중 k개를 택해야한다. 이때 각각의 색이 인접하지 않기 위해서는 간격이 (k-1)개 필요하다.

4. 이웃하지 않은 순열의 수는 combination으로 구할 수 있다.

 

import math
n, k = int(input()), int(input())
if k > n/2:
    print(0)
else:
    print((math.comb(n-3 - (k-2), k-1) + math.comb(n-1 - (k-1), k)) % 1000000003)

아래는 숏코딩으로 짧게 만들어 본 코드.

from math import comb as c
n,k=map(int,open(0))
print(0 if k>n/2 else (c(n-k-1,k-1)+c(n-k,k))%(10**9+3))

dp를 활용한 풀이는 아래와 같다.

mod = 10**9+3 
n = int(input()) 
k = int(input()) 
dp = [[0] * (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): 
        if i == n: 
            dp[i][j] = (dp[i - 3][j - 1] + dp[i - 1][j]) % mod
        else: 
            dp[i][j] = dp[i - 1][j] + dp[i - 2][j - 1] % mod
print(dp[n][k])

일직선이라 생각하고 dp를 구하되, 맨 마지막 n번째에 대해서는 1번째와 원형으로 만난다는 것을 고려해 별도의 조건을 부여하는 방법이다.