[백준 02482] 색상환 [Java]

문제

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

---

풀이

바텀업보다 탑다운 방식으로 접근하면 쉬워지는 문제다.

 

원형을 이루는 N개의 색상환 표에 대해 인접하지 않은 색을 K개 선택하는 경우의 수를 구해야 한다.

경우의 수가 너무 커지지 않게 1e9 + 3으로 나눈 나머지를 출력해야 한다.

 

dp[N][K] : N개의 색상에 대해 인접하지 않는 K개의 색을 선택하는 경우의 수

문제를 단순화해보자. 다음이 성립한다.

• dp[N][1] = N
• if K > N / 2, dp[N][K] = 0

문제에서 주어진 그림을 예시로 설명하겠다.

우선 빨강색(N번째)을 선택해보자.

N번째 색을 선택할 때, 인접한 N - 1번(다홍색)은 선택할 수 없다. N - 2번(주황)을 선택해야하고, 이 때 K - 1개의 색을 선택하면 된다.

dp[N][K] = dp[N - 2][K - 1]

N번째 색을 선택해봤다면, 이제는 N번째 색을 선택하지 않고, N - 1번째 색으로 선택해 탐색해보자.

dp[N][K] = dp[N - 1][K] + dp[N - 2][K - 1]

---

소스코드

보기