문제
https://www.acmicpc.net/problem/2482
색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(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초, 메모리 128MB이다.
큰 문제를 더 작은 문제들로 분할해서 생각을 해보자.
이러한 접근은 문제를 다이나믹 프로그래밍으로 해결할 수 있게 도와준다.
가장 기초가되는 단서들을 일단 모두 찾아본다.
K==1인경우.
N이 어떤값이라도, N개 선택할 수 있다.
그리고 색상환표의 원형을 선형으로 풀어서 생각을 해보자.
중요한것은 인접한것을 고를 수 없다는 것이지 원형이라는 사실이 아니다.
이제 N이 6이라고 가정을 하고, 생각을 해보자.
첫 번째 아이템을 선택했다고 가정을 해보자.
인접한 색상에 해당하는 두번째와 마지막 (노란색 원)은 선택할 수 없는 색상이다.
첫번째 색상을 선택한 경우.
-> N-2개의 색상 중에서, K-1개를 다시 선택해야 한다.이제 빨간색 아이템을 선택하지 않았다고 가정해보자.
노란색과 파란색 원들 중에서 다시 고를 수 있다.
첫번째 색상을 선택하지 않은경우
-> N-1개의 색상 중에서, K개를 다시 선택한다.N개중 K개를 선택하는 방법은 아래와 같다.
dp[i][j] : i개중 j개를 선택하는 방법.
dp[i][j] = dp[i-2][j-1] + dp[i-1][k]숫자가 너무 커질 수 있으므로 문제에서 제시한 10억3으로 나누는것을 잊지말자.
- 궁금할만한 내용
Q : N개의 색상이 존재하는데, 왜 첫번째를 선택한 경우와 선택하지 않은 경우에 대해서만 고려하고 있나요?
A : 첫번째를 고르지 않았다면, N-1개의 색상 중에서 K개를 다시 선택하는
소문제에서 나올 수 있는 경우의 수를 찾게 되는데, 소문제에서 다시 첫번째 색상을 고르는 경우, 큰 문제에서 두번째 색상을 고르는 경우가 됨.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N, K;
static int[][] dp;
final static int DIVIDER = 1000000003;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
N = stoi(in.readLine());
K = stoi(in.readLine());
dp = new int[N + 1][N + 1];
for (int i = 0; i <= N; ++i) {
dp[i][1] = i;
dp[i][0] = 1;
}
for (int i = 4; i <= N; ++i) {
for (int j = 1; j <= K; ++j) {
dp[i][j] = (dp[i - 2][j - 1] % DIVIDER + dp[i - 1][j] % DIVIDER) % DIVIDER;
}
}
System.out.println(dp[N][K]);
}
private static int stoi(String s) {
return Integer.parseInt(s);
}
}