[Baekjoon] 1149번 : RGB거리 (Python)

Python

방법 1 - 메모리 30864KB / 시간 112ms / 코드 길이 492B

규칙은 3개지만 코드를 사용함에 있어 볼 규칙은 하나이다.

바로 이전에 있는 집의 색과 다른 색을 칠해야한다는 것.

이것을 위해서 집별 RGB를 저장하는 list와 별개의 list를 구성하여 이전 집에 대한 색을 제외한 나머지 두 색에 대한 최소값을 계속 더해 Memorization 하는 것이 Point

물론 반대로 생각해서 내가 지금 택한 집의 색이 존재하고 다른 색을 선택한 이전 집을 계속 더해가며 최소값을 구하는 방법도 존재함.

가령 현재 집이 빨강 R이었다면 이전 집은 파랑 B 혹은 초록 G를 선택해야 한다.

n = int(input())
l = [[0]*3 for _ in range(n)]
t = [[0]*3 for _ in range(n)]

for i in range(n):
    l[i][0], l[i][1], l[i][2] = map(int, input().split())

for i in range(n):
    if i == 0:
        t[i][0] = l[i][0]
        t[i][1] = l[i][1]
        t[i][2] = l[i][2]
        continue
    t[i][0] = l[i][0] + min(t[i-1][1], t[i-1][2])
    t[i][1] = l[i][1] + min(t[i-1][0], t[i-1][2])
    t[i][2] = l[i][2] + min(t[i-1][0], t[i-1][1])

print(min(min(t[n-1][0], t[n-1][1]), t[n-1][2]))

방법 2 - 메모리 30864KB / 시간 76ms / 코드 길이 263B

방법 1을 조금 간소화 한 버전

import sys

n = int(input())
l = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

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

print(min(l[n-1]))