[알고리즘] 백준 1149번
문제
https://www.acmicpc.net/problem/1149
풀이
먼저 Input을 약간 헷갈렸다. 첫번째 입력 N은 집의 갯수이고 두번째 부터는 집마다 칠하는 색의 비용을 입력해주는데 위의 문제처럼 26, 40, 83을 입력하면 첫번째 집을 빨간색으로 칠하는데 비용은 26, 초록색으로 칠하는데는 40 그리고 파란색으로 칠하는데는 83의 비용이 든다는 의미입니다.
또한 문제에 나와있듯이 이웃한 집은 같은 색으로 칠할 수 없습니다. 저는 아직 많이 부족하여 역시 잘하시는 분들의 블로그들에서 힌트를 얻어 풀었습니다. 그래도 조금은 문제를 풀어서 그런지 다이나믹 프로그래밍으로 풀어야한다는 것은 알았습니다!
제가 이해하고 만든 풀이와 제 의식의 흐름은 다음과 같습니다.
- 바로 전 집까지의 비용의 최소합과 현재 칠할 수 있는 색 중의 최소 값을 합하면 현재까지 칠한 색의 비용은 최소합이 됩니다.
- 하지만 인접한 집은 같은 색을 칠할 수 없다는 조건으로 인해 현재 집을 어떤 색으로 칠하냐에 따라 최소의 비용은 달라지게 됩니다.
- 저는 현재 집의 칠하는 색에 따라 나오는 이전의 칠한 색의 비용들을 최소들을 모두 구하기로 했습니다. 이런식으로 마지막 집에서도 빨강, 초록, 파랑을 칠함에 따른 이전 집들의 색칠 비용들의 최소합을 구하였습니다. 그리하여 마지막 색이 빨강일때, 초록일때, 파랑일때의 합들 중 최소 값을 구하면 모든 집을 칠할 수 있는 최소합을 구할 수 있습니다.
코드는 다음과 같습니다.