[BOJ] 1149번 RGB거리 - 파이썬

📒 문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

✏️ 풀이

개인적으로 dp문제에 많이 약하다. 그래서 기초부터 해보기위해 이런저런 문제들을 풀어보는 중인데, 이 문제도 조금 어렵게 느껴졌다.

처음에는 2차원 리스트로 dp리스트를 만들어서 이전의 집이 RGB중 어떤 집이었는지 체크를 하며 넘어가려 했는데, 효율적이지 못할 것이라고 생각이 들어 포기했다.
그러다가 dp리스트를 따로 만들지 말고, 그냥 주어진 입력 리스트를 활용하여 어차피 3가지인 경우의 수를 모두 구해보며 min값을 찾으면 될 것이라고 생각이 들어 다음의 코드를 작성했다.

n = int(input())
rgb_list = []
for i in range(n):
    rgb_list.append(list(map(int, input().split())))

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

메모리는 29452kb, 시간은 104ms로 적당한 결과를 얻을 수 있었다.