백준 2449번 전구

사용한 알고리즘: DP


 문제에 주어진 조건에 따라 N개의 전구들을 하나의 색으로 바꾸는 최소 횟수를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 6~7)
 'dp[a][b] : a~b 전구를 같은 색으로 바꾸는 최소 횟수' 라고 설정하였습니다.
 모든 묶음 (a~b) 는 무조건 맨 앞 a전구 색으로 맞춰져 있다고 생각하겠습니다.
 사실 잘 생각해보시면 (a~b) 전구 묶음을 맨 앞의 a전구 색으로 맞춰도 오류가 없습니다...

(2) (코드 15~17)
 기저경우인 2개묶음을 먼저 계산해 줍니다. 모든 전구를 바로 옆 전구와 묶어줍니다.
 두 전구의 색이 같은경우 dp[i][i+1] = 0 이고, 두 전구 색이 다른경우 이를 맞춰주는 한번의 횟수 dp[i][i+1] = 1 라고 설정해 줍니다.
 1개의 묶음 dp[i][i] = 0 임은 자명합니다...

(3) (코드 19~35)
 3개 묶음, 4개 묶음, ... , N개 묶음 으로 전구들을 묶어봅니다.
 (k-1개의 묶음) a 전구부터 a+k 전구까지의 횟수  dp[a][a+k] 는 전체 a~a+k를 2개 묶음으로 나누어, 이를 합치는 경우들 중 최소 횟수의 값입니다.
 예를들어 a, a+1, a+2, a+3 전구들을 묶는 dp[a][a+3]의 계산은 다음 경우를 고려해야 합니다.
 1. a / a+1~a+3         -> dp[a][a] + dp[a+1][a+3] ( a와 a+1 색이 다르면 ) +1
 2. a~a+1 / a+2~a+3  -> dp[a][a+1] + dp[a+2][a+3] ( a와 a+2 색이 다르면 ) +1
 3. a~a+2 / a+3         ->  dp[a][a+2] + dp[a+3][a+3] ( a와 a+3 색이 다르면 ) +1
 위의 1,2,3 중 최소 값이 dp[a][a+3] 값이 됩니다.