✨백준 1149 RGB 거리✨

import sys
input = sys.stdin.readline

num = int(input())

bill = [list(map(int,input().strip().split(" "))) for _ in range(num)]

for i in range(1,num):
    bill[i][0] = min(bill[i-1][1], bill[i-1][2])+ bill[i][0]
    bill[i][1] = min(bill[i-1][0], bill[i-1][2])+ bill[i][1]
    bill[i][2] = min(bill[i-1][0], bill[i-1][1])+ bill[i][2]
           
#print(case) 
print(min(bill[num-1][0],bill[num-1][1],bill[num-1][2]))

나름 엄청난 걸 배운 것 같아서 반짝이를 붙여줬다!!

매 순간 가장 나은 것을 고른다 라는 말이 참 애매했다.
그 순간 최상의 선택을 한다는 관점을 착각해서 이번 문제를 몹시 헤맨것 같다.

처음의 접근 방법은

import sys
input = sys.stdin.readline

num = int(input())

bill = [list(map(int,input().strip().split(" "))) for _ in range(num)]
check = [0 for i in range(num)]

case = [0 for i in range(3)]
for i in range(3):
    check[0] = i
    case[i] += bill[0][i]
    for k in range(1, num):
        temp = sorted(bill[k])
        #print(temp)
        # 1등 가능
        if check[k-1] != (for_index := bill[k].index(temp[0])):
            #다음으로 작은애를 구해내야함 
            case[i] += temp[0]
            check[k] = for_index
        #다음으로 가벼운 애
        else:
            check[k] = bill[k].index(temp[1])
            case[i] += temp[1]
    print(check)
           
print(case) 
print(min(case))

으로 접근했다. 하지만 이 풀이의 맹점은 index 함수는 리스트 속 중복된 값이 존재한다면, 인덱스가 가장 작은 값을 반환한다는 것이다.

cf) 값이 리스트 속에 존재하지 않는다면 에러 뜸

따라서 위의 풀이는 인덱스를 메모한 상태로 접근하는 풀이기에 예제 5번에서 틀린 값이 출력되었다.

import sys
input = sys.stdin.readline

num = int(input())

bill = [list(map(int,input().strip().split(" "))) for _ in range(num)]
check = [0 for i in range(num)]

case = [0 for i in range(3)]
for i in range(3):
    check[0] = i
    case[i] += bill[0][i]
    #print(bill[0][i])
    for k in range(1, num):
        temp = sorted(bill[k])
        if check[k-1] != (for_index := bill[k].index(temp[0])):
            case[i] += temp[0]
            #print(temp[0])
            check[k] = for_index
  
        else:
            if bill[k].count(temp[0]) > 1:
                check[k] = bill[k].index(temp[0],for_index+1)
                #print(check[k])
                #print(temp[0])
                case[i] += temp[0]
            else:  
                check[k] = bill[k].index(temp[1])
                case[i] += temp[1]
                #print(temp[1])
    #print(check)
           
#print(case) 
print(min(case))

count 함수를 사용하여 리스트 속의 해당 값이 1개 이상이라면 다음 인덱스를 반환하게끔 조건을 걸었다.
하지만 이 풀이 또한 틀렸다. 처음엔 도무지 왜 틀린지 감이 오지 않아 손으로 그려보았다.
저 관점에서 그림을 그리며 푸니 답은 내 코드와 동일하게 나왔다. 고민을 하다 혹시 경로 자체가 틀린것이 아닌가란 생각이 불현듯 들었다.

이 접근 방식의 맹점은 이때까지의 모든 값을 다 더한 현재 지점까지 도달하기에 최상의 점을 선택하는 것이 아닌, 무조건 첫번째 고른 색깔을 골랐다는 가정하에 최상을 선택하는 것이었다

관점이 잘못되었던 것이다 😲 정말로 생각치 못했다.
항상 그 순간 최상을 선택하자! 라는 말에 주안점을 둔 탓에 그 순간 최상을 고르는 형식으로 풀어왔다. 풀면서도 항상 이게 전체에서 최상의 선택이 보장이 되는가에 대한 의문이 들었었다.
역시 아니였다.
앞으로 문제를 풀 때는, 그 순간 딱 앗 이게 좋아보이는데 라는 다음을 고르는 입장 말고 다음 선택을 해야하는 대상 입장에서 이때까지 중 최적의 해를 가지고 와야겠다라는 생각이 들었다.

따라서, 이 지점에서 시작했다. 앞으로 제일 좋아 보이는 선택지를 골라나가자! 라는 관점이 아닌, 이 지점에 도달하기 위해서는 이때가지 앞서 있었던 값들 중 어떠한 것을 골라야할지의 관점으로 문제를 풀어야겠다.

이 지점에 도달하기 위해서!! 완전 중요!!!