2482_색상환

https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net dp를 2차원배열로 설정해서 풀 수 있다. dp[i][j]라면 i개의 색중에서 j개의 색을 선택하는 것이다. dp를 채워나간다고 생각해보자. 만약 dp[i][j]를 채운다고 생각해보자. i번째 색이 새로 추가되었다면 그 색을 칠하는 경우와 안 칠하는 경우 2가지가 나올 것이다. 만약 색이 추가되었다면 i-1번째색은 칠할 수 없고, 이때 색을 칠한다면 j-1개를 구해야 하므로 i-2 개의 색으로 j-1개의 색을 칠하는 경..