BAEKJOON 9461
문제
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다.
각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로, 초록으로, 파랑으로 칠하는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.
시간 제한
나의 처음 코드
이 문제는 이웃되는 집끼리는 같은 색을 가질 수 없는 조건을 가지고 있다. 또한 시간제한도 매우 짧은 0.5초를 가지고 있다. 통상적으로 1초에 1억번의 연산을 하는 것을 생각해봤을 때 N이 1,000이므로 O(N^2) 도 가능할 것으로 예측된다.
그러나 마땅한 아이디어가 또오르지 않아서, 백트래킹 방식으로 구현을 했다. 안 된다는걸 알면서 일단했다,,, 시도 안하고 답지 보는게 마음에 걸려서,,, 그 코드는 아래와 갔다.
import sys
N = int(input())
color_of_each = [list(map(int, input().split())) for i in range(N)]
price_min = 10000001
def find_min(hidx : int, idx : int, price : int):
global price_min
if hidx == N:
price_min = price if price_min > price else price_min
return
if price_min < price:
return
for i in range(3):
if i == idx:
continue
price += color_of_each[hidx][i]
find_min(hidx+1, i, price)
price -= color_of_each[hidx][i]
find_min(0, -1, 0)
print(price_min)
결과는 시간 초과. 당연히 시간 초과 뜰 줄 알고있었다. 자, 그러면 어떠한 방식으로 이 문제를 풀어야 할까?
처음에 입력받은 RGB의 집을 첫 번째 집이라고 했을 때, 점차 쌓아가는 방식으로 문제를 플어야 함을 대략적으로 느낄 것이다.
즉, 시간을 줄이는 대신 메모리를 늘려가는 방식으로 푼다고 생각하면 된다. 메모라이징 을 통해서 이 문제를 접근해 보자.
간단한 예시로, 입력이 다음과 같다고 하자40 15 20
15 30 20
1 100 200. 그렇다면, 두 번째 행에서는 첫 번째 행에서 가질 수 있는 최소를 가져야하고, 세 번째 행에서는 두 번째 까지 합친 것들 중에 최소를 가져가야 한다. 다음 코드를 함께 봐보자.
N = int(input())
color_of_each = [list(map(int, input().split())) for i in range(N)]
price_min = 10000001
dp_list = [color_of_each[0]]
for i in range(1, N):
temp_list = []
temp_list.append(min(dp_list[i-1][1], dp_list[i-1][2]) + color_of_each[i][0])
temp_list.append(min(dp_list[i-1][0], dp_list[i-1][2]) + color_of_each[i][1])
temp_list.append(min(dp_list[i-1][0], dp_list[i-1][1]) + color_of_each[i][2])
dp_list.append(temp_list)
print(min(dp_list[N-1]))
맞았습니다 보시다 싶이, for문 안에서 위에서 설명한 작업을 해주고 있다. 첫 번째 행은 dp_list에 먼저 넣어주고, 위에서 설명한 작업을 계속 하는 것이다. 두 번째 행에서 R값을 골랐을 때, G, B에서 고를 수 있는 최소 값을 더해서 저장해준다. G값을 골랐을 떄도, B값을 골랐을 때도 똑같이 해주면 된다. 그러면 마지막에 붙은 리스트중 min값이 최소 비용이 되는 것이다.
역시 dp문제는 내가 너무 약하다,,, 더 열심히,,,