오늘의 한 마디
경우의 수를 dp 배열의 값으로 만들 수도 있구나... 생각을 유연하게!
- Baekjoon 문제 링크
- 현재 백준 문제집: 단기간 성장을 풀고 있습니다.
문제
색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(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) 으로 나눈 나머지를 출력한다.
예제 입력 1
4
2예제 출력 1
2발상
N색상환에서 인접하지 않도록 K개의 색을 선택하는 경우의 수
Dynamic Programming 문제이긴 한데, 다음의 특징점이 있다.
- 원형이다.
- 최적해를 찾는 것이 아니라 경우의 수를 찾는다.
dp 배열을 어떻게 만들어야 할지 도무지 감이 안 와서 해설을 봤다.
해설
dp[i][j] : 1~i번째 색만 가지고 인접하지 않도록 j개의 색을 선택하는 경우의 수
경우의 수를 기준으로 한 최적해 구하기 문제로 환원할 수 있다.
for i in range(N+1):
for j in range(K+1):
...
dp[i][j] = dp[i-1][j] + dp[i-2][j-1]마치 조합의 합 공식을 연상시킨다.
- i번째 색을 포함시키지 않고 j개의 색을 선택하는 경우의 수 :
dp[i-1][j] - i번째 색을 반드시 포함시키고 j개의 색을 선택하는 경우의 수 :
dp[i-2][j-1]- 이때에는 i-1번째 색도 포함시키지 못한다!
그리고, 원형 dp이기 때문에 마지막 N번째 색을 추가할 때는 예외적인 조건이 필요하다.
- N-1번째 색 뿐만 아니라 1번째 색도 사용하지 못하기 때문에,
dp[i-3][j-1]으로 점화식을 만들어야 한다. - 하지만 N번째 색을 포함시키지 않고 만드는 경우에는, 1번째 색을 사용해도 무관하기 때문에 여전히
dp[i-1][j]이다.
풀이
N = int(input())
K = int(input())
# https://ca.ramel.be/149
# dp[i][j] : 1~i번째 색 중에서 j개의 색을 선택하는 경우의 수
dp = [[0]*(K+1) for _ in range(N+1)]
# 반드시 N>=4, K>=1
for i in range(N+1):
for j in range(K+1):
if j == 0:
dp[i][j] = 1
continue
if j == 1:
dp[i][j] = i
continue
dp[i][j] += dp[i-1][j]
dp[i][j] += dp[i-2][j-1] if i != N else dp[i-3][j-1] # n번째 색을 반드시 고른 경우면, 1번째와 n-1번째 색은 못 고르니까.
dp[i][j] %= 1_000_000_003
print(dp[N][K])