문제 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 순열 조합과 비슷한 DP문제. 개인 적으로는 결국 조합의 경우 수 모두 찾아보기 때문에 배낭 알고리즘(Knapsack)과 비슷한 부분이 있는 것 같다. 해당 문제에서도 배낭 문제처럼 idx번째 색을 선택한 경우와 선택하지 않는 경우를 아래와 같이 표현할 수 있다. 1. idx 색을 선택: dp[idx-2][k-1] 인접 칸을 한 칸 띄워 idx-2로, 색 한 개를 선택하였으므로 남은 선택 색상 개수를 -1 해..