[BOJ] 1149. RGB거리(Python) / DP

www.acmicpc.net/problem/1149

1149번: RGB거리

실버 1 문제라 간단한 DFS로 Brute Force(완전탐색)으로 풀릴 줄 알았는데, 47%에서 시간초과 나더라..

# 소요시간 20분

DFS 완전탐색으로 접근한 파이썬 코드는 다음과 같다.(47%에서 실패한 코드)

---

from sys import stdin
input = stdin.readline

def dfs(depth, temp):
    global MIN
    if temp > MIN:      # 가지치기
        return
        
    if depth == N:
        MIN = min(MIN, temp)	# 최솟값 갱신
        return
        
    for i in range(3):
        if check[depth-1][i]:
            continue
        check[depth][i] = 1
        dfs(depth+1, temp + A[depth][i])
        check[depth][i] = 0

# main
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
check = [[0] * 3 for _ in range(N)]
MIN = float('inf')
for i in range(3):
    check[0][i] = 1
    dfs(1, A[0][i])
    check[0][i] = 0
print(MIN)

---

금방 이 길이 아님을 깨닫고, 바로 DP로 접근했다.

직접 손으로 DP 테이블을 그려보니 어렵지 않았다.

• 열 크기도 R, G, B로 총 3개밖에 되지 않았고, N은 주어졌다.
• Input 받은 맵(dp)에 그대로 1번째 행부터 차례로 현재 행의 한줄 위의 행에서 자신의 열이 아닌 다른 열의 숫자 중에 더 작은 수를 택해 현재 자신의 위치의 수에 더해준다.
• 마지막 줄(N-1)까지 DP테이블을 구성하는 작업이 끝나면 N-1행의 최솟값을 출력한다.

 

DP로 접근한 파이썬 코드는 다음과 같다.(성공코드)

# 소요시간 20분

---

from sys import stdin
input = stdin.readline

N = int(input())
dp = [list(map(int, input().split())) for _ in range(N)]

for i in range(1, N):
    for j in range(3):
        dp[i][j] += min(dp[i-1][:j] + dp[i-1][j+1:])

print(min(dp[N-1]))

---

• 시간 : 124ms / 메모리 : 123268KB

---

둘다 같은 DP인데 어차피 열은 R, G, B 세 개밖에 되지 않으므로 이중포문 대신 직접 구현할 수도 있다.

리스트 슬라이싱과 같은 불필요한 연산을 하지도 되기 때문에 시간, 메모리를 더 절약할 수 있다.

보다 효율적인 파이썬 코드는 다음과 같다.(성공코드)

from sys import stdin
input = stdin.readline

N = int(input())
dp = [list(map(int, input().split())) for _ in range(N)]

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

print(min(dp[N-1]))

---

• 시간 : 108ms / 메모리 : 123036KB
• 고찰 : 쉬운 수준의 DP문제였다. 조금만 더 생각했으면 완탐 해보기 전에 DP를 떠올렸을 것이다. 조금 더 생각한다면 시간, 공간적으로 더욱 효율적인 코드를 짤 수 있을 거다!