RGB라서 처음에는 픽셀 그런 느낌인 줄 알았는데 말 그대로 빨 초 파 색칠하는 비용 구하기였다.
→RGB거리←
문제
이해하기 쉽게 그림으로 설명하자면,
이렇게 인접하는 집끼리만 색깔이 다르면 된다!!
최종적으로 칠했을 때 그 비용이 최소인 경우를 찾으면 된다.
일단 한 집마다 선택지는 3개다. 하지만 이전 집에서 선택한 것을 빼야하기에 선택지는 2로 줄게 된다.
맨 첫집부터 차례대로 선택하고 비용을 비교하면서 최소가 되는 선택지를 찾으면 완성이다!
코드
dp = []
N = int(input())
for i in range(N):
dp.append(list(map(int, list(input().split()))))
for i in range(1, N):
dp[i][0] = min(dp[i][0]+dp[i-1][1],dp[i][0]+dp[i-1][2])
dp[i][1] = min(dp[i][1]+dp[i-1][0],dp[i][1]+dp[i-1][2])
dp[i][2] = min(dp[i][2]+dp[i-1][0],dp[i][2]+dp[i-1][1])
print(min(dp[N-1])) 먼저 dp 배열에 RGB 3개씩 배열로 받아 [N * 3] 2차원 배열로 구성했다.
(dp[i][0,1,2] ← 이게 0, 1, 2 각각 R, G, B를 나타낸 것이다.)
2번째 집부터 선택하면서 이전 집에서 선택한 비용과 현재 집에서 선택한 비용의 합이 최소인 것을 고르면 된다.
이때 이전 집에서 선택한 색과는 다른 색을 골라야 하기 때문에 각각의 색을 선택할 때 비교는 선택한 색과 다른 색을 골랐을 때랑 해야한다.
설명이 조금 복잡한데, 쉽게 말해서
3번째 집에서 선택을 한다고 하면 RGB 3가지 색을 선택할 수 있다.
만약 3번째 집 R 선택했을 때,
그러면 (3번째 집 R + 2번째 집 G) 과 (3번째 집 R + 2번째 집 B) 중에 최소를 고르면 된다.
이전 상황에서 2번째 집 배열에는 각각의 색을 선택했을 때 최소 비용이 이미 저장되어 있을 것이다.
그렇다면!!
N 번째 집까지 가면 자동으로 N번째 집에 R G B 색을 골랐을 때의 최소비용이 저장되어 있다.
이때까지 풀어왔던 바름업 방식이다.
Review
뭔가 다이나믹 프로그래밍 방식을 쉽게 이해할 수 있게 만든 문제인 것 같다.
이전의 값을 기억해서 효율적으로 해답을 찾는다...
원래 RGB 각각의 값 구할 때 그냥 3번 반복해서 코드를 깔끔하게 정리할려 했는데... 내 머리로는 안되더라
그리고 dp 배열이랑 input 배열을 따로 설정할수도 있고 같은 배열로 쓸수도 있는데 이번 문제에서는 같이 했다. 그게 뭔가 깔끔하다랄까..
근데 무조건 따로 설정해야하는 문제도 있었던 것 같다.
문제를 많이 풀어보면 볼수록 그런 디테일한 감들이 점점 익혀지는 것 같다.(아직 초짠데 이런 거 적으니까 좀 웃기네 ㅋ)
벨로그에는 아직 안올렸지만 벌써 스트릭 18일째다!!
중간중간에 시간 없어서 사칙연산도 몇개 있긴 한데 그래도
꾸준히 하는 중이다!!!
