실버 I

💡문제 분석 요약

동적 계획을 사용한 문제 풀이

💡알고리즘 설계

이중 리스트 a에 입력 값을 받는다.

a를 돌면서 이전 값의 최솟값을 더한 값을 구하여 현재 돌고 있는 곳에 업데이트 한다.

모든 값을 돌고 난 뒤, n번을 돌아 저장된 값이 있는 n-1 배열에 있는 값 중 최솟값을 출력한다.

💡코드

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

a = [0]*n
for  j in range(n):
    a[j] = list(map(int,input().strip().split()))
for i in range(1,n):
    a[i][0] = min(a[i-1][1],a[i-1][2])+a[i][0]
    a[i][1]= min(a[i-1][0],a[i-1][2]) + a[i][1]
    a[i][2]= min(a[i-1][0],a[i-1][1]) + a[i][2]

print(min(a[n-1][0],a[n-1][1],a[n-1][2]))

💡시간복잡도

for문 N 2번 N^2

💡 틀린 이유

우선 처음 접근 방식이 잘못 됐다. 딱 봤을 때 이전 문제 영향으로 graph의 가중치를 고려하는 다익스트라로 풀수 있지 않을까? 했다가 구현이 애매해져서 포기하고 비고란을 보게 되었다.

돌이켜 보면 각 집에서 최적해(최소 값)을 골라서 더한다고 해도 처음 r,g,b 값에 의해 뒤에 선택할 수 있는 해가 아예 달라져 버린다. 따라서 초기 r,g,b값을 정해두고, 그에 따라 최적해를 골라 최종 값의 후보를 알고, 거기에서 min값을 결정해야한다.

dp라는 것을 알았으나 구현을 제대로 하지 못했다. 이전 값을 알면서도 이것을 어디에다가 저장해야하지? 싶었다. 그래서 r,.g,b의 값을 다 저장해놓은 리스트를 3개 만들어서 구하려고 하다보니, 메모리 소비가 커져보였다.

결국 코드를 봤고, 놓친 부분은 list를 이중으로 둬서 n집에 0,1,2로 rgb값을 저장하면 된다.

a[n] = [r.g.b] 이런식으로..

그리고 데이터를 r,g,b리스트에 각각 저장해야하는 것이 아닌,

i를 둘러 볼때 i값은 이미 안 상태에서 변경하면 된다. 그러면 i 값을 잃어버리지 않은 채 최적값으로 업데이트 가능하다.

일단 너무 먼저 선택하고 그다음에 반영해야한다는 고정관념을 갖고 있었다. r을 선택했다면 이 값을 어디에 저장해야 활용하지? 그 다음 값의 g,b를 알아야 하므로 다음값에 더해서 판단할 수 없을텐데? 라는 생각으로 이어진 듯 하다.

이 코드는 현 상황에서 r을 선택하면, 이전에는 무조건 r이 아닌 g,b,를 택했을테니 현재 보는 집에 이전 것과 비교해서 업데이트를 해주는 방식이다.

💡 기억할정보

  • 여러 값을 저장할 때 2중 리스트를 활용하고, 이전 값을 현재에 업데이트 하여 접근한다.