[백준] No.2482 - 색상환 (C++)

문제

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

2482번: 색상환

 

풀이

순열 조합과 비슷한 DP문제.

개인 적으로는 결국 조합의 경우 수 모두 찾아보기 때문에 배낭 알고리즘(Knapsack)과 비슷한 부분이 있는 것 같다.

 

해당 문제에서도 배낭 문제처럼 idx번째 색을 선택한 경우와 선택하지 않는 경우를 아래와 같이 표현할 수 있다.

 

1. idx 색을 선택: dp[idx-2][k-1] 

인접 칸을 한 칸 띄워 idx-2로, 색 한 개를 선택하였으므로 남은 선택 색상 개수를 -1 해준 k-1로

 

2. idx 색을 선택하지 않음 : dp[idx-1][k]

 색을 선택하지 않았으므로 바로 이전 색인 idx-1, 색을 선택하지 않았으므로 k는 그대로

 

따라서 1번째 색에서 현재의 색 idx까지의 색 중에선 k개를 선택한 경우의 가지 수는 

dp[idx][k] = dp[idx-2][k-1] + dp[idx-1][k] 로 표현할 수 있다.

 

추가적으로 k=0인 경우의 dp값들은 정답에 도달하였으므로 1로 설정해두고 n개의 색들에서 1개만 선택하는 경우는 n가지의 가지 수가 나오기 때문에 미리 dp[n][1] 은 모두 0으로 설정한다.

 

최종적으로 만약 우리가 첫 번째 색을 선택한다면 마지막 색은 인접 색이 되므로 선택해서는 안된다는 예외가 발생한다.

첫번째 색을 선택하였다고 가정하면 해당 색과 인접한 두 색은 선택할 수 없으므로 dp[color_num-3][select_num-1]과 같은 값이다. 이 값과 첫 번째를 제외하고 색을 선택하는 경우, dp[color_num-1][select_num]를 합진 값이 정답이다.

 

dp[color_num-1][select_num]+ dp[color_num-3][select_num-1]

 

+ 나머지 연산에 주의하자.

 

코드