백준 17404 RGB 거리 2

 

조건

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

1번과 N번집의 색이 달라하여 인접한 집끼리는 같은 색을 가지면 안된다.

 

문제 생각

1번 집의 색을 정함으로써 1번집의 비용과 마지막 집의 비용 범위 (첫번째 집 비용 제외 나머지 두개)를 결정하게 된다

 

1.첫집의 최소 비용을 결정 한 후 각 분기별로 최소 비용값 탐색하기 , 

 

 

 최선인지 확인하며 분기탐색하기  (n번값 선택시 나눠지는 분기값 + 그다음분기값) 

각 범위의 값을 탐색하며 최소값 구하기 

각 집의 색 범위 안에서 최소값 갱신하며 첫 집을 선택분기로 최소값 구하기

import sys
input =sys.stdin.readline

INF = 400000000
n= int(input())

color_values = [list(map(int,input().split())) for __ in range(n)]


#시작과 끝은 색이 달라야한다.
#각 노드의 인접노드와 색이 달라야한다.

# 시작점과 끝점 값 비교해서 시작값 끝값 절대값으로 결정
# 중간노드 선택 분기 나눠서 가기?
# last_n = {1:[0,2], 2:[1,0],0:[1,2]}

result=INF
for i in range(3):
    dp = [[INF,INF,INF] for __ in range(n)]
    dp[0][i] = color_values[0][i]
    for j in range(1,n):
        dp[j][0] = min(dp[j-1][1],dp[j-1][2]) +color_values[j][0]
        dp[j][1] = min(dp[j-1][0],dp[j-1][2]) +color_values[j][1]
        dp[j][2] = min(dp[j-1][1],dp[j-1][0]) +color_values[j][2]
    dp[j][i] =INF
    curMin  = min(dp[n-1])
    result = min(result,curMin)
print(result)

첫집을 정한 후 진행 가능한 분기에서 최소값 갱신 (첫 출발 집 외의 출발지는 INF값 지정)

최소 값을 갱신하며 INF값의 경로로 들어온 값들은 저절로 걸러지게 된다.

 

마지막집에서 첫집과 같은 색이면 안되기에 처음엔 딕셔너리로 i값에 따라 결정값을 변경하려했다.

다른 사람의 코드를 보고 그냥 간단하게 INF처리를 하게되면 저절로 필터링된다는것을 알고 INF로 처리했다.