BOJ(RGB거리)(1149)

작성일 | In

RGB거리 1149

  • SWM에서 풀었던, 배열의 최소합 구하는 문제와 매우 비슷하다.
  • 재귀로 풀 수 있는 모든 문제는 다른 함수로 변환해서 풀 수 있다.
  • 그런데 시간 제한이 0.5초이다. 1초에 1000ms인걸 감안해서, 재귀로 풀면 파이썬에서는 시간초과가 나지 않을까도 싶다.

  • 애초에 DP문제이기 때문에 DP로 접근해보자

  • i-1,i,i+1이 연속이다. DP의 중요 조건인 연속이 들어가 있다.

  • 연속이다 -> i-1과 i가 연속이면, 재귀적으로 집이 5개라고 하면, 앞만 색을 다르게 칠하면 조건을 적용할 수 있다.

  • D[i][j] = i번 집을 색 j로 칠했을 때, 1~i번 집을 칠하는데 드는 비용의 최솟값
    • j = 0 => 빨강
    • j = 1 => 초록
    • j = 2 => 파랑

  • D[i][j] = > i번 집을 j로 칠했을 때, 1~i번 집을 칠하는 데 드는 비용의 최솟값

  • 예를 들어 빨강이 D[i][0]이라고 하면
  • 초록은 D[i-1][1] 파랑은 D[i-1][2]일 것이며 이 둘을 min한 값에 빨강으로 집을 칠한 값 A란 배열에 있다면, + A[i][0]로 나타낼 수 있다.
  • 초록이라면 : D[i][1] = min(D[i-1][0],D[i-1][2])+ A[i][1]을 구하면 된다.

점화식

  • D[i][0] = min(D[i-1][1], D[i-1][2]) + A[i][0]
  • D[i][1] = min(D[i-1][0], D[i-1][2]) + A[i][1]

  • D[i][2] = min(D[i-1][0], D[i-1][1]) + A[i][2]

  • 문제의 정답은 min(D[N][0], D[N][1], D[N][2])가 된다.
N = int(input())
a = [[0]*3]+[list(map(int, input().split())) for _ in range(N)]
d = [[0]*3]+[[0]*N for _ in range(N)]
for i in range(1, N+1):
    d[i][0] = min(d[i-1][1], d[i-1][2]) + a[i][0]
    d[i][1] = min(d[i-1][0], d[i-1][2]) + a[i][1]
    d[i][2] = min(d[i-1][0], d[i-1][1]) + a[i][2]
print(min(d[N][0], d[N][1], d[N][2]))

참고자료 codeplus

0%