알고리즘 문제
[백준] 1149번 RGB 거리
feelcoding
2020. 1. 12. 20:04
728x90
단계별로 풀어보기 동적계획법1의 5단계 문제
1149번: RGB거리
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.
www.acmicpc.net
이렇게 제출했는데 런타임 에러가 났다
def promising(row, color):
if row == 0:
return True
if col[row - 1] == color:
return False
else:
return True
def locate(row):
if row == n:
total.append(cost[row - 1])
return
for i in range(3):
if promising(row, i):
col[row] = i
cost[row] = cost[row - 1] + li[row][i]
locate(row + 1)
n = int(input())
li = []
from sys import stdin
for i in range(n):
li.append(list(map(int, stdin.readline().split())))
col = [0] * n
cost = [0] * n
total = []
locate(0)
print(min(total))
5일 뒤 2020.01.18 재도전
1932번을 풀고 나니까 이 문제도 어떻게 푸는지 딱 보였다.
이렇게 쉽게 풀 수 있었는데 괜히 시간 낭비를 한 것 같지만 덕분에 또 하나 더 배웠다. 앞으로는 절대로 잊지 말아야지
1932번과 같이 뒤에서부터 풀면 된다.
n = int(input())
li = []
from sys import stdin
for i in range(n):
li.append(list(map(int, stdin.readline().split())))
for i in range(n - 2, -1, -1):
for j in range(3):
if j == 0:
li[i][j] = min(li[i][j] + li[i + 1][1], li[i][j] + li[i + 1][2])
elif j == 1:
li[i][j] = min(li[i][j] + li[i + 1][0], li[i][j] + li[i + 1][2])
else:
li[i][j] = min(li[i][j] + li[i + 1][0], li[i][j] + li[i + 1][1])
print(min(li[0]))
728x90