오늘의 문제
https://www.acmicpc.net/problem/1149
포인트 쳌쳌
- 첫번째 집에서 색깔을 red, green, blue 각각을 고를 경우 나눠지는 가짓수를 생각해보자.
- 각 집이 선분으로 이어져있다고 가정할 때, 접하는 집들간의 색깔은 달라야 한다.
- 다이나믹 문제답게 메모이제이션을 사용해보자.
풀이 코드
처음 시도한 코드
n = int(input())
charge = [0]*n
preIdx = -1
for i in range(n):
colors = list(map(int, input().split()))
m = min(colors)
if preIdx == 0:
m = min(colors[1], colors[2])
if preIdx == 1:
m = min(colors[0], colors[2])
if preIdx == 2:
m = min(colors[0], colors[1])
charge[i] = m
preIdx = colors.index(m)
#print(charge)
print(sum(charge))
이 코드는 시작이 어떤 색깔이냐와 상관없이 그리고
이전 집의 색깔이 무엇이냐(preIdx)를 보고 무조건 최소비용만을 고르도록(min함수) 했다.
결과는 틀렸고, 이 코드의 오류는 두가지이다.
- min() 반환값과 중복값이 여러 개일 경우 무조건 앞쪽에 위치한 비용만 고름 => 특정 경우에 대한 탐색을 할 수 없게 된다.
- 반례는 다음과 같다.
5 5 5 4 1 1 5 3 5 4 5 2 1 3 5 # answer: 12
- 반례는 다음과 같다.
- 첫번째 집에서의 비용이 최소가 아니더라도 총 누적 비용이 최소일 수 있다.
- 반례는 다음과 같다.
101 100 101 100 1 100 # answer: 101
더 많은 반례는 이 게시글을 확인해보면 좋을 것 같다.
- 반례는 다음과 같다.
정답 코드
이 코드는 이전 집까지의 누적비용(sum_[i-1])에다가
현재 접근한(인덱스 i) 집의 색깔(red는 0, green은 1, blue는 2)을 칠할 때의 비용을 합하여 결과를 낸다.
가장 마지막 집까지(n-1) 순회했을 때 세 가지의 결과값이 정해지며, 이때 min()으로 최소값을 찾아 출력해준다.
n = int(input())
sum_ = [] #결과 저장 리스트
cost = [] #비용 저장 리스트
for i in range(n):
cost.append(list(map(int, input().split())))
sum_.append([0]*3)
for i in range(n):
if i == 0:
sum_[i] = cost[i]
else:
sum_[i][0] = cost[i][0] + min(sum_[i-1][1], sum_[i-1][2])
sum_[i][1] = cost[i][1] + min(sum_[i-1][0], sum_[i-1][2])
sum_[i][2] = cost[i][2] + min(sum_[i-1][0], sum_[i-1][1])
print(min(sum_[n-1]))