[백준] DP<5> 색상환(feat. 조합)
1. 문제 소개
주어진 N개의 색상에 대하여 서로 인접하지 않게 K개를 뽑는 문제이다. 이때 주어진 N개의 색상은 원형으로 주어져 있다. 즉 N = 8이라고 주어졌을 경우 1번 색과 8번 색은 서로 인접하는 경우인 것이다.
예를 들어 N = 4, K = 2가 주어지면 [1,3], [2,4] 의 2개의 경우의 수를 고를 수 있으므로 답은 2다.
N = 4, K = 3 이 주어진다면 가능한 조합의 수는 없다.
2. 풀이 알고리즘 with DP
DP의 유용함은 기어이 조합 문제에도 마수를 뻗치기 시작했다.
문제를 본다면 주어진 N개에 대하여 K개를 고르는(순서없이) 문제이기 때문에 조합을 사용할 수 있을 것 같다.
먼저 DP table을 설계해보자.
2차원 dp를 준비하고 각각의 열과 행을 다음과 같이 설정해준다.
dp[고를 수 있는 색의 수][고를 색의 수] = 경우의 수
이때 경우의 수는 원형이 아닌 직선에서의 경우의 수를 가정한다.
초기값(dp[1][0], dp[1][1] = 1)을 설정해주고, 반복문으로 값을 채워준다.
1
2
3
4
5
6
7
8
9
for i in range(2 ,N+1):
for j in range(1, N+1):
if j == 1: # 색을 하나만 고르는 경우는 전체 색상 갯수와 같음.
dp[i][j] = i
elif i > j:
# i번째 색을 선택하지 않는 경우: i-1개의 색 중에서 j개를 선택하는 경우와 같음
# i번째 색을 선택하는 경우: i-2개의 색 중에서 j-1개를 선택하는 경우의 수
dp[i][j] = dp[i-2][j-1] + dp[i-1][j]
이때 고를 색의 수(j 인덱스)가 1이라면 전체 색의 수를 한 가지씩 고를 수 있으므로 경우의 수는 i가 된다.
이외의 경우의 수는 점화식을 따라준다.
dp[i][j] = dp[i-2][j-1] + dp[i-1][j]
이때, 조합의 수학적 점화식을 알고 있다면 dp[i-2][j-1]이 아닌 dp[i-1][j-1]이 와야한다고 생각할 수도 있다.
하지만 일반적인 조합의 식과 이 문제에서의 조합의 식은 조건이 다르다.
우리는 인접한 색상을 고를 수 없다.
즉 i번째 색을 선택했을때, 반드시 i-1 번째의 색은 고를 수 없으므로 남은 i-2개의 색상 중에서 j-1개를 뽑는 경우의 수가 남는다.
해당 코드를 통해 직선에서 인접하지 않는 경우의 수를 만들 수 있다.
이제 원형에서 해당 문제를 생각해보자. 우리에겐 2가지 경우의 수가 있다.
첫 번째 색을 고르는 경우
→ 2번, 마지막 번호의 색은 고를 수 없으므로 N-3 개에서 K-1개의 색을 고르는 조합
(전체 N개에서 1번, 2번, N번째 제외하므로 N-3개, 이미 1번 색을 뽑았기 때문에 K-1개를 고른다.)
첫 번째 색을 고르지 않는 경우
→ 나머지 N-1개에서 K개를 고르는 조합.
해당 조건을 통해 원형 조건을 해결해 줄 수 있다. 이 조건만 지켜준다면 나머지 조합은 직선에서의 경우의 수와 같게 된다.
3. 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import sys
read = sys.stdin.readline
DIVINER = 1000000003
N = int(read())
K = int(read())
# 경우의 수
# 1. 맨 앞의 색을 고르는 경우
# 1번 2번, 제일 마지막 색은 고를 수 없으므로 N-3 중 K-1개의 색 고르기(첫번째를 이미 골랐으므로 K-1개)
# 2. 맨 앞의 색을 고르지 않는 경우
# 나머지 N-1개에서 K개 고르기
# dp -> dp[색상 갯수][고를 색의 수]
# 직선에서의 경우임.
dp = [[0]* (N+1) for _ in range(N+1)]
dp[1][0] = 1
dp[1][1] = 1
for i in range(2 ,N+1):
for j in range(1, N+1):
if j == 1: # 색을 하나만 고르는 경우는 전체 색상 갯수와 같음.
dp[i][j] = i
elif i > j:
# i번째 색을 선택하지 않는 경우: i-1개의 색 중에서 j개를 선택하는 경우와 같음
# i번째 색을 선택하는 경우: i-2개의 색 중에서 j-1개를 선택하는 경우의 수
dp[i][j] = dp[i-2][j-1] + dp[i-1][j]
if K == 1:
print(N)
else:
print((dp[N-3][K-1] + dp[N-1][K])%DIVINER)