[BOJ/Step15] 1149 : RGB거리 (Python)

www.acmicpc.net/problem/1149

1149번: RGB거리

---

처음에는 RGB 각각 시작해서 3가지 루트를 계산해서 최솟값을 출력하도록 했음

각각 출발해서 RGB중

이전 위치 제외하고 남은 둘 중 작은값이랑 작은값 인덱스를 같이 리턴하는 함수를 만들어서

최종 값 최솟값을 출력하게 풀었음

 

하 예제도 뭐도 다 잘 나오는데 틀렸다고 해서 대체 뭐가 틀린건지

반례 다 찾아서 입력해봤는데 다 맞는거야 젠장

그래서 뒤지고 뒤져서 반례 찾았는데 같은 값이 들어오면 둘 중 뭐가 작은지 구분을 못한다는게 문제였음

 

그래서 이걸 어떻게 구현하나 한참 고민하다가 모르겠어서 구글링 했는데

사람들이 하나같이 같은 방법으로 풀었고 나는 그 방법을 이해 못함...

 

1. 각 비용을 리스트 house에 저장

2. 두번째 R = (첫번째 G, 첫번째 B 중 작은 값) + 두번째 R 비용

    두번째 G = (첫번째 R, 첫번째 B 중 작은 값) + 두번째 G 비용

    두번째 B = (첫번째 R, 첫번째 G 중 작은 값) + 두번째 B 비용

3. n번째 R = (n-1번째 최종 G, n-1번째 최종 B 중 작은 값) + n번째 R 비용

    n번째 G = (n-1번째 최종 R, n-1번째 최종 B 중 작은 값) + n번째 G 비용

    n번째 B = (n-1번째 최종 R, n-1번째 최종 G 중 작은 값) + n번째 B 비용

 

2번은 이해를 했다 이거야 n번째 값 구하려면 n-1번째 두개 비교해서 작은 값 더하는거

근데 만약에 n번째 R 구하는데 n-1번째 G가 B보다 작아 그럼 n-1번째 최종 G를 더해야 되는거 아닌가???

왜 최종 값을 비교하지??? 대체 왜??

 

최종 값을 비교하면 안되는거 아닌가

최종은 크더라도 단일 값은 작을 수 있잖아 ㅜ

제일 작은거 고르는거 아니야?ㅜㅜ 최

종만 작으면 되서 상관없는거야??

진짜 아무리 쳐다봐도 왜인지 모르겠음 하 설명해줄사람?

 

# 1149.py

n = int(input())

house = [[0] * 3 for i in range(n)]
for i in range(n):
    house[i][0], house[i][1], house[i][2] = map(int, input().split())

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

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

 

 

+ 뒤에 문제 계속 풀다보니 이해함.. 걍 내가 DP에 대한 이해가 한참 모자란듯 ㅜ