RGB거리 2 (17404번) - 백준 (BOJ)

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

17404번: RGB거리 2

 

백준 - RGB거리 2 (17404번)

 

난이도 : Gold 4

알고리즘 : Dynamic Programming

풀이 소요 시간 : 60분

 

import sys
input = sys.stdin.readline


def main(N):
    INF = (N+1) * 1000
    R, G, B  = map(int, input().split())
    R2, G2, B2  = map(int, input().split())
    
    rr = gg = bb = INF
    rb, rg, gr, gb, br, bg =\
        R+B2, R+G2, G+R2, G+B2, B+R2, B+G2
        
    for _ in range(N-2):
        R, G, B = map(int, input().split())
        rr, rg, rb, gr, gg, gb, br, bg, bb =\
        min(rg, rb) + R, min(rr, rb) + G, min(rr, rg) + B,\
        min(gg, gb) + R, min(gr, gb) + G, min(gr, gg) + B,\
        min(bg, bb) + R, min(br, bb) + G, min(br, bg) + B
    return min(rg, rb, gr, gb, br, bg)


if __name__ == '__main__':
    lowest_cost = main(int(input()))
    print(lowest_cost)

 

DP를 활용해서 푸는 문제였다.

 

총 N개의 집에서, x번째 집의 색을 칠할 때,총 9가지 상태가 존재하는데

R~~~~R
R~~~~G
R~~~~B
G~~~~R
G~~~~G
G~~~~B
B~~~~R
B~~~~G
B~~~~B

이렇게 9가지다.

 

예를 들어

1. R(GBG)R + G
2. R(BRG)B + G

이렇게 2가지 경우의 수가 있다고 할 때,

두 경우 모두 처음 집은 R, 현재 집은 G로 색칠돼있다.

 

결국 두 경우 중 비용이 작은 최솟값 하나만, R~~~G 섹션에 저장해두면 된다.

이렇게 DP를 활용하면, O(N)의 시간복잡도로 문제를 해결할 수 있다.

 

예전에 이미 풀었던 문제였는데,

너무 오랜만에 다시 풀다보니 DFS + DP로 접근하다가 시간 초과가 발생했다.

그리고 다시 위처럼 DP만 활용해서 해결했다.