[Python] 백준 풀기 1149 - RGB거리

파이썬 백준 1149번

실버1

https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

 

 

문제 보기

 

 

 

문제 풀기

전체 비용의 최솟값을 찾기 위해서 이전 집까지 나온 비용을 계속 비교해 봐야 한다.

그리고 이전 집과 다음 집의 색과 겹치지 않게 하기 위해서 세 가지 색상인 빨강, 초록, 파랑을 기준을 잡고 이 전 색깔의 경우를 생각해 본다.

이 두 가지를 상기하면서 따져보게 되면, 빨강을 기준으로 잡았을 때 이전 집은 초록과 파랑이 가능하다. 이 두 색깔 중 작은 비용을 현재 빨강의 비용과 합치게 되고 이 합은 다음 집의 비교 대상이 된다.

house_ls[i][0] = min(house_ls[i-1][1], house_ls[i-1][2]) + house_ls[i][0]

이렇게 연속적으로 비교하는 dp 식이 작성되고 초록, 파랑에 대해서도 모두 따져보게 되면, 최종적으로 이차원 리스트 마지막 원소에 그 세 가지에 대한 합 리스트가 저장된다. 마지막 리스트의 최솟값을 return 해주고 결과를 얻는다.

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def fnDPMinimumBudget(N, house_ls):
    for i in range(1, N):
        # 빨강
        house_ls[i][0] = min(house_ls[i-1][1], house_ls[i-1][2]) + house_ls[i][0]
        # 초록
        house_ls[i][1] = min(house_ls[i-1][0], house_ls[i-1][2]) + house_ls[i][1]
        # 파랑
        house_ls[i][2] = min(house_ls[i-1][0], house_ls[i-1][1]) + house_ls[i][2]
        print(f'house_ls in fn: {house_ls}')            # test print
    return min(house_ls[-1])


if __name__ == "__main__":
    N = int(inputdata().strip())
    house_ls = [list(map(int, inputdata().split())) for _ in range(N)]
    print(f'house_ls: {house_ls}')          # test print
    
    result = fnDPMinimumBudget(N, house_ls)
    print(result)



# 3
# 26 40 83
# 49 60 57
# 13 89 99

# house_ls: [[26, 40, 83], [49, 60, 57], [13, 89, 99]]
# house_ls in fn: [[26, 40, 83], [89, 86, 83], [13, 89, 99]]
# house_ls in fn: [[26, 40, 83], [89, 86, 83], [96, 172, 185]]

# 96