백준 1149번 RGB거리 (Python, DP, Silver1)

백준 1149번 RGB거리

문제 접근

이 문제를 사실 보자마자 완전탐색으로 풀어야겠다~라고 생각했다.
사실 되게 안좋은 습관인데 요즘 풀었던 문제들이 대부분 완전탐색으로 풀렸기 때문에 안일하게 생각했던 것 같다.
우선 완전탐색이 안되는 이유는 N이 1000까지이다. 따라서 전의 집을 제외하고 칠해야 하기 때문에 3*2^1000번의 계산을 해야한다. 중간에 가지치기로 cost가 최소 cost보다 크다면 종료하는 문을 넣었지만 백준 44%에서 멈추는 것을 볼 수 있었다.

따라서 DP를 생각했다. 일정한 공식(점화식)이 있으면서 수행시간도 빠르게 가져갈 수 있기 때문에 DP를 생각했다. 아래 문제 풀이에서 이에 대해 설명하겠다.

• 점화식 세우기
• 점화식 구현

문제 풀이

완전탐색 코드

완전탐색으로 풀었던 코드는 아래와 같다.
index를 1 증가시키면서 color를 다른 color를 사용하여 cost에 추가해주고 이를 마지막에 result와 비교하며 result값을 갱신한다. 이렇게 해줘도 최악의 경우에는 결국 3*2^1000번의 계산을 해야하기 때문에 시간초과가 발생한다.

import sys
N = int(sys.stdin.readline())
house = []
for i in range(N):
    color = list(map(int, sys.stdin.readline().split()))
    house.append(color)

result = float('inf')

def select(index, color_index, cost):
    global result
    if index == N:
        if result > cost:
            result = cost
        return

    if result <= cost:
        return

    if color_index!=0:
        select(index+1, 0, cost + house[index][color_index])
    if color_index!=1:
        select(index+1, 1, cost + house[index][color_index])
    if color_index!=2:
        select(index+1, 2, cost + house[index][color_index])

select(0,0,0)
select(0,1,0)
select(0,2,0)
print(result)

DP 점화식 세우기

DP 점화식은 조금 간단하다. 내가 빨간색으로 i번째의 색을 칠하고 싶다면 i-1번째까지의 cost가 최소인 루트를 기용하여 칠해야 한다. 이때는 i-1번째의 색이 파란색 또는 초록색이어야 한다.
그렇다면 i번째 집의 빨간색 cost가 30이라면

dp[i][빨강] = min(dp[i-1][초록], dp[i-1][파랑]) + 30 이 되어야 한다.

따라서 점화식은 위와 같이 나온다.

이를 구현하기

따라서 2차원 dp를 선언하고 첫번째 인덱스는 집, 두번째 인덱스는 선택한 색깔이다.
따라서 dp의 마지막에 3개의 색깔을 선택한 코스트가 들어간다. 이 중에서 최소인 값이 전체 cost의 최솟값이다.

dp = [[0 for i in range(3)] for i in range(N+1)]

for i in range(1,N+1):
    dp[i][0] = min(dp[i-1][2],dp[i-1][1]) + house[i][0]
    dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + house[i][1]
    dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + house[i][2]
   
print(min(dp[N]))

제출 코드

DP 사용 코드

import sys
N = int(sys.stdin.readline())
house = [[0,0,0]]
for i in range(N):
    color = list(map(int, sys.stdin.readline().split()))
    house.append(color)

result = float('inf')

dp = [[0 for i in range(3)] for i in range(N+1)]

for i in range(1,N+1):
    dp[i][0] = min(dp[i-1][2],dp[i-1][1]) + house[i][0]
    dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + house[i][1]
    dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + house[i][2]

print(min(dp[N]))