백준 1149 RGB거리

백준 1149 RGB거리 dp 알고리즘을 활용한 풀이법

해당 문제는 dp 알고리즘을 활용하여서 계산의 반복을 줄이면서 최소값을 찾는 문제이다.
처음에는 완전탐색을 이용해서 풀으려고 했지만 시간복잡도가 너무 많아질 것 같아서 포기했다.

그래서 백트래킹 알고리즘도 생각은 해보았지만 그래도 dp 알고리즘이 맞다고 생각했다.

사실 아직도 어떤 경우에 어떤 알고리즘이 정확하게 맞는지는 헷갈린다.

특히나 그리드, dp, 완전탐색은 경우가 명확히 보이지 않는 경우가 많아서 그런거 같다... ㅠㅠ

파이썬 코드

n = int(input())
rgb = []

for _ in range(n):
  rgb.append(list(map(int, input().split())))

for i in range(n):
  p = rgb[i]

  if i == n-1:
    nex = [0, 0, 0]
  else:
    nex = rgb[i+1]
  
  nex[0] = min(nex[0] + p[1], nex[0] + p[2]) 
  nex[1] = min(nex[1] + p[0], nex[1] + p[2])
  nex[2] = min(nex[2] + p[0], nex[2] + p[1]) 

print(min(rgb[n-1]))

집을 색칠하는 비용에 대한 것을 점점 반복문을 지날수록 업데이트 되는 환경으로 코드를 짰다.

결국 이전에 했던 계산이 현재 계산에 영향을 미치기 때문에 dp알고리즘을 활용하여 문제를 풀지 않았나 싶다.

편안하게 dp 알고리즘을 활용할 수 있는 그날까지!! 화이팅