[백준 1149] RGB 거리 (python)

https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

RGB 거리 문제

문제 자체는 동적 계획법을 활용하여 푸는 문제이다. 사실 아직 동적 계획법이 뭔지 몰라서 최대한 힌트 없이 조건에 맞춰서 풀려고 했으나 실패했다. 항상 문제 접근을 단순하게 시작하는 편인데, 너무 단순하게 생각하니까 조건하나씩 빼먹기도하고, 알고리즘 개념을 제대로 공부해서 적용할 필요가 있을거 같다.

# 입력조건
import sys
N = int(sys.stdin.readline())
RGB = [0]*N
for x in range(N):
    RGB[x] = list(map(int, sys.stdin.readline().split()))

for i in range(1, N):
    # 다음 RGB의 각 인덱스에 대해 이전값 중의 해당 값 제외한 RGB 중의 최솟값의 누적합
    RGB[i][0] = min(RGB[i-1][1], RGB[i-1][2])+RGB[i][0]
    RGB[i][1] = min(RGB[i-1][0], RGB[i-1][2])+RGB[i][1]
    RGB[i][2] = min(RGB[i-1][0], RGB[i-1][1])+RGB[i][2]
print(min(RGB[N-1]))

코드 자체는 굉장히 쉽다 

사실상 입력조건 제외하고는 for문 1개로 바로 해결되는 문제다.

RGB의 다음 칸(i)의 값이 이전 칸(i-1)의 값 중 해당 값을 제외한 RGB 중의 최솟값을 누적합 해가는 방법으로 풀 수 있다.

위 식처럼 풀면 각 루트에 대하여 최소 값만 더해주니까 결과값에 대해서 최소값을 구하면 바로 해를 구할 수 있다.

반응형

---

느낀점

실버 1 급의 문제지만 실제론 생각만 해내면 바로 풀어낼 수 있어서 엄청 어려운 문제는 아니었다. 하지만 자꾸 조건 하나씩 잘못 생각하니까 이상한 길로 빠져서 해결이 어려웠다.

문제에 주어진 조건을 잘 파악하고 깔끔하게 정리하고, 어떤 개념을 적용하면 되는지 잘 파악하기 위해 차근차근 풀어봐야겠다.