백준 2482 (C++) 색상환

최초 업로드: 2025-04-27 06:12:48

최근 수정 시간: 2025-07-25 09:01:55

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] 색상환

[문제 링크](https://www.acmicpc.net/problem/2482)

## 문제 설명

색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다.

그림 1. 먼셀의 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) 으로 나눈 나머지를 출력한다.

## 풀이
#### dp[i][j][k]를 i번 색을 마지막으로 선택하고, 총 j개의 색을 선택했을 때, k는 첫번째 색의 선택 여부일 때의 경우의 수로 두고 풀었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

// dp[i][j][k] : i번 색을 마지막으로 선택하고, 총 j개를 선택했을때의 경우의 수, k는 첫번째 색을 포함했는지 여부.
const long long MOD = 1e9+3;
long long dp[1000][1001][2];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, K; cin >> N >> K;

dp[0][1][1]=1;
 for(int i=1;i<N;i++) {
 dp[i][1][0]=1; // i번째 색을 처음으로 선택함.
 for(int j=0;j<i-1;j++) {
 for(int k=0;k<K;k++) {
 for(int l=0;l<2;l++) {
 dp[i][k+1][l] = (dp[i][k+1][l] + dp[j][k][l]) % MOD; // j번을 마지막으로 선택하고 총 선택 수가 k개인 것에서 추가로 i번을 더 선택함.
 }
 }
 }
 }

long long total=0;
 for(int i=0;i<N-1;i++) {
 total += dp[i][K][0]+dp[i][K][1];
 }
 total = (total + dp[N-1][K][0]) % MOD; // 마지막 색을 선택하면 처음 색을 선택하면 안됨.

cout << total;
}
```