[ BOJ 오답노트 ] 1149 파이썬 : RGB거리

2022 03 22

 

1. 틀린 기록

 

 

 

2. 원인 분석

- 일단 틀린 내용은 없지만 정말 오랫동안 고민했고, 다른 분들 코드를 보고 풀었기 때문에 오답노트를 했다.

- 이 문제는 분명히 다이나믹 프로그래밍인데, 도저히 어떻게 dp를 사용해야할 지 감이 안 잡혔다.

- 모든 경우의 수를 다 따져봤을 경우에는 시간 초과 판정이 날 것이라고 생각했다.

 

 

 

3. 해결

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

for i in range(n):
    lst = list(map(int, input().split(' ')))
    rgb.append(lst)

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

    # G
    rgb[i][1] = min(rgb[i-1][0], rgb[i-1][2]) + rgb[i][1]

    # B
    rgb[i][2] = min(rgb[i-1][0], rgb[i-1][1]) + rgb[i][2]

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

- i가 0일 때부터 생각하지 말고, i가 1일때 0번째를 생각하는 방식이다.

- 0번째에서 1번째를 고르고, 1번째에서 2번째를 고르는 경우에는 선택한 RGB 중에서 최소를 골라도 그 다음번 째의 값이 최소라고 보장할 수 없기 때문이다.

- 뒤에서 앞을 선택하면 그 전을 고려하지 않아도 된다. 너무 횡설수설이지만.. 아무튼 그렇다.

 

 

 

4. 배운 점

- 시간이 지나서 이 문제를 다시 보면 과연 내가 잘 풀 수 있을 지.. ㅎ 그래도 0번째부터 연산을 수행하는 것이 아니라 그 다음에서 시작하여 그 전 선택지들을 고르는 것이 매우 신선했다.

- DP의 또 다른 응용 방법이라고 생각하고 앞으로 써먹을 문제가 있었으면 좋겠다.