C - 17404 RGB거리 2

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

 

https://github.com/shirohebiui/BAEKJOON/blob/0a00624f43bbbc313ae13481f9595c19ddaf46ba/%23DP/G/17404(G4)/17404%20solve.c

 

 

dp i 번째에는 그 상태의 최선의 비용이 들어가야한다. 곰곰히 고민해보다가 1차원배열으로 dp[i]에 최선의 값을 넣으면 그 후

dp[i]에서 R을 선택한 후 i+1번째에서 G, B 비용이 dp[i]를 초과하고 R선택이 최선이면

다시 뒤로 돌아가서 i+1번째에서 R을 선택할 수 있도록 해야한다.

이 문제는 DP고 DP에 이딴방식은 존재하지 않으니 어떻게 해야할지 고민하다

i번째 까지의 최선의 비용이 아니라

i번째의 R, G, B를 고를 경우의 최선의 비용을 dp에 저장코자해야한다는걸 깨달았다.

따라서 dp를 2차원배열, 각 행에 RGB를 골랐을경우의 최선의 비용이 저장되도록했다.

dp[i][R] [i][G] [i][B]같은 느낌으로 저장하는 것이다. (C언어로 구현함으로 0=R, 1=G, 2=B)

 

따라서 점화식은

현재색을 선택했을때 최선의 비용  = 현재색의 비용 + 이전집에서 현재색과 다른색비용중 최솟값

dp[i][color] = RGB[i][color] + min(dp[i-1][!color]) //현재 고른 color가 아닌선택지중 작은값

이런 형식이 될 것이다.

 

이를 구현하면 아래와 같다.

void dpfunc() { 
    for(int i=1; i<N; i++) {
        DP[i][0] = RGB[i][0] + min(DP[i-1][1], DP[i-1][2]); 
        //R consider prev G,B
        DP[i][1] = RGB[i][1] + min(DP[i-1][0], DP[i-1][2]); 
        //G consider prev R,B
        DP[i][2] = RGB[i][2] + min(DP[i-1][0], DP[i-1][1]); 
        //B consider prev R,G
    }
}

 

이리하여 1~N까지의 집에 칠하며 N번째에 R, G, B를 골랐을 경우의 최소비용(best)를 구할 수 있게 됐다.

하지만 집은 링형태로 N과 1은 서로 이웃하므로 같은 색을 고르면 안된다.

그런데 위의 방법은 N번째에 고른 최적의 비용이 1번째에 무엇을 골랐는지 보장,확인이 불가능한 구조이다.

 

이 문제를 해결하는것은 그냥 무식하게 1번째에 R고르기, G고르기, B고르기 세개의 경우를 정해놓고 각 케이스마다

탐색을 하기로 했다.

이러면

R을 골랐을때 N번째에선 G,B -> ex) best = min(best, dp[N-1][G],dp[N-1][B]  

G를 골랐을때 N번째에선 R,B

B를 골랐을때 N번째에선 R,G

이렇게 N번째에서 어떤 값이 유효한 값인지 미리 정해두고

N까지 탐색한후 N번째에서 유효한선택지만 보고 최선의 비용을 찾는것이다.

 

고르는 방법은 R을 선택했을땐 R외의 값의 비용을 INF로 바꿔 선택하는 경우가 최악이므로 자연히 선택이 안된경우로 최선의 비용이 도출될 것이다.

이를 구현하면 아래와 같다. 

int find_best() {
    int best = 1000*N;
    for(int select = 0; select < 3; select++) {
        DP[0][select] = RGB[0][select];
        DP[0][(select + 1) % 3] = INF;
        DP[0][(select + 2) % 3] = INF;
        dpfunc();
        best = min(best, min(DP[N-1][(select + 1) % 3], DP[N-1][(select + 2) % 3]));
    }
    return best;
}