백준 1149번 문제(RGB거리) 파이썬(Python) 풀이 [로밍맨]

문제 링크

www.acmicpc.net/problem/1149

1149번: RGB거리

 

정답 코드는 아래와 같습니다.

def solve():
  n = int(input())
  rst = []
  r, g, b = [int(x) for x in input().split()]
  rst.append((r, g, b))
  for _ in range(1, n):
    r, g, b = [int(x) for x in input().split()]
    pR, pG, pB = rst[-1]
    R = r + min(pG, pB)
    G = g + min(pB, pR)
    B = b + min(pR, pG)
    rst.append((R, G, B))
  fR, fG, fB = rst[-1]
  print(min(fR, fG, fB))
 
solve()
 

 

이 문제의 핵심은 결국 다음과 같은 점화식(수학적으로 정확한 표현은 아님)이 성립하는 것을 파악하는 것에 있습니다.

S(k, r) = curr r + min(S(k-1, g), S(k-1, b))

r, g, b 는 각각 red, green, blue 를 의미하고, k는 현재 위치를 의미합니다.

S(k, r) 이라 함은 k번째 위치의 red 가 칠해지는 경우의 비용의 최소값(정답)을 의미합니다.

cur r 은 현재(k번째) 위치의 red를 칠하는 비용을 의미합니다.

위 식은 red 에 대한 식인 것이고, green, blue 각각에 대해서도 모두 성립합니다.

 

식으로 쓰니까 뭔가 복잡해보이지만 사실 말로 풀어쓰면 꽤 간단합니다.

현재 위치의 집을 빨간색으로 칠하려는데 필요한 최소 비용은 현재 집을 칠하는 비용에다가, 그 바로 직전까지 칠한 비용을 더한 것입니다.

그런데 그 직전에 칠한 집은 현재 칠하려는 집과 색이 같으면 안되니까 확인해봐야 하는 것은 green과 blue의 값이 되는 것이고, 비용을 최소화 하고 싶기 때문에 그 중에서 더 작은 값을 선택한다는 것입니다.

 

728x90

 

점화식이 완성된 이후에는 단순하게 해당 로직을 코드로 옮겨주는 작업입니다.

전형적인 DP(dynamic programming)문제 이며, bottom-up 방식으로 구현하였습니다.

 

DP문제의 풀이는 크게 top-down 방식과 bottom-up 방식으로 나눌 수 있는데요.

top-down 방식은 보통 재귀적으로 구현되고, bottom-up 방식은 반복문을 사용하여 구현되기 마련입니다.

파이썬은 다른 언어에 비하여 재귀 호출의 횟수에 제약이 크기 때문에 파이썬으로 DP를 구현하시는 경우에 가능하면 저의 풀이처럼 bottom-up 방식을 사용하시길 권장드립니다.

 

참고로 언어와 상관없이 재귀 방식은 함수 호출 오버헤드로 인하여 거의 항상 반복문을 이용하는 방식보다 더 느립니다.

 

풀이는 아래 영상을 참고 바랍니다.

www.youtube.com/watch?v=YUtGZ2AQ2Rc

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)