문제
풀이
dp문제이다. dp는 아직 많이 어려운 것 같다. dp[N][M] = N개의 색깔 중 인접하지 않게 M개를 칠하는 경우의 수를 의미한다. dp[i][j]는 i번째를 j번째 색깔로 칠하는 경우와 칠하지 않는 경우로 나뉜다. 칠하는 경우는, i번째가 j번째로 칠해져 있기 때문에 dp[i-2][j-1]의 경우의 수(i-2번째에 j-1번째 색깔을 칠하는 경우의 수)와 같다. 칠하지 않는 경우는, i번째 칠하지 않았으므로 dp[i-1][j]의 경우의 수(i-1번째에 j번째 색깔을 칠하는 경우의 수)와 같다. 그러므로, dp[i][j] = dp[i-2][j-1] + dp[i-1][j]이다. 마지막 N번째의 경우는 첫번째와 고려해야하기 때문에, N번째를 칠하는 경우는 N-1번째와 1번째를 모두 칠하지 않아야하므로 N-3개 중 M-1개를 인접하지 않게 칠하는 dp[N-3][M-1]과 같고, N번째를 칠하지 않는 경우는 dp[N-1][M]의 경우의 수와 같다. 그러므로 최종 정답은 dp[N][M] = dp[N-3][M-1] + dp[N-1][M] 이다. 초기값은 M = 0인 경우는 무조건 1개, M=1인 경우는 총 색깔의 갯수만큼의 경우의 수가 있으니 설정해준다.
소스 코드
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
#include <iostream>
#include <vector>
#define MOD 1000000003
int main(){
int N, M;
scanf("%d", &N);
scanf("%d", &M);
int dp[1001][1001]; // dp[N][M] = N개의 컬러중 인접하지 않게 M개를 선택한 경우의 수
for(int i = 0 ; i<=N; i++){
dp[i][0] = 1;
dp[i][1] = i;
}
for(int i = 2; i<N; i++){
for(int j = 2; j<=M; j++){
dp[i][j] = (dp[i-2][j-1]%MOD + dp[i-1][j]%MOD)%MOD;
}
}
dp[N][M] = (dp[N-3][M-1]%MOD + dp[N-1][M]%MOD)%MOD;
printf("%d\n", dp[N][M]);
}
