[BOJ] 2482번 : 색상환

1. problem : 

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

 

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n, k; 
const int val = 1004;
const int mod = 1e9 + 3;
int d[val][val]; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n >> k; 
	if (k == 1) {
		cout << n; 
		return 0; 
	}

	for (int i = 1; i <= n; i++) {
		d[i][0] = 1;
		d[i][1] = i;
	}
	for (int i = 3; i <= n; i++) {
		for (int j = 2; j <= k; j++) {
			d[i][j] = (d[i - 2][j - 1] + d[i - 1][j]) % mod;
		}
	}
	int ans = (d[n - 3][k - 1] + d[n - 1][k]) % mod;
	cout << ans;
}

source code 참고 : https://akim9905.tistory.com/71

[백준] 2482번 색상환

 

dp를 이용해 풀어야 한다. 여기서 d라는 테이블은 선형에서의 경우의 수를 나타낸다. d [4][2]라고 하면, 색상이 4개 있고, 2개를 뽑을 때 경우의 수다. 따라서, 마지막 색상을 택하느냐, 아니냐에 따라서 경우를 나눠줘야 한다. 

이때는, d[2][1] (마지막 색상을 뽑았을 때) + d [3][2] (마지막 색상을 뽑지 않았을 때)가 d [4][2]가 된다. 

그리고 마지막 int ans를 출력할 때는 d[n-3][k-1] + d [n-1][k]로 구하는데, 그 이유는 고리형태이기 때문이다. 만약에 마지막 색상을 뽑았을 때는 n-1번째와 1번째는 사용하지 못한다. 따라서 d [n-3][k-1]이 나온다. 반면, 마지막 색상을 뽑지 않았을 때는 d [n-1][k]가 나오게 된다.