[백준 1149] RGB거리

[BanApp]

pypy3

import sys

n = int(sys.stdin.readline())

arr = []

for i in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))

for i in range(1,len(arr)):
    arr[i][0] = min(arr[i-1][1],arr[i-1][2]) + arr[i][0]
    arr[i][1] = min(arr[i-1][0],arr[i-1][2]) + arr[i][1]
    arr[i][2] = min(arr[i-1][1], arr[i-1][0]) + arr[i][2]

print(min(arr[-1]))

DP문제라고? 최소비용을 구하고 싶다고? 그럼 min함수 쓰는 문제임.
만들 수 있는 작은값으로 계속 만들어나가면 된다. 0번에 집 지으면 1,2,번만 집을 지을 수 있다.
이전에 나올 수 있는 조합중에 작은것만 신경쓰면서 가면 된다.
쉽게 생각하면 첫번째 뭘 고르는지가 중요한데 그걸 알 수 없으니깐 첫번째 출발지점에 있는 애들로 부터 전부 출발해서 전부 최소값을 만들어 보자!
이게 이 문제의 취지다. 그중에서 최소값이 위 문제의 조건으로 만들 수 있는 최소값이기 때문이다.

BFS 골드 문제만 보면 풀기가 싫어집니다.. 도와주세요 찬희짱...

[ghdcksgml1]

학교에서 만나면 BFS 공부하는것을 좀 도와드리죵