14. 동적 계획법 1
CLASS 4 ESSENTIAL
인접한 집에 같은 색을 칠하지 않는다는 조건 하에 모든 집에 페인트를 칠할 때 드는 최소 비용을 구하는 문제입니다. 브루트 포스를 사용하여 최소값을 구하기에는 경우가 너무 많습니다(\(3\times 2^{n-1}\)). 따라서 DP를 이용해서 빠르게 구해야 합니다. 저장할 것은 마지막으로 칠한 집의 색이 각각 R, G, B일 때 최소로 필요한 비용으로 하겠습니다. 그러면 첫 번째 집은 그 집을 칠하는 비용이 첫 번째 집까지 칠하는 데에 필요한 최소 비용이 되고, 두 번째 집부터는 이전 집에 칠한 색에 영향을 받습니다. 이전 집이 R이라면 이번 집은 G 또는 B를 칠해야 합니다. 반대로 생각하면 이번 집이 G라면 이전 집은 R 또는 B가 칠해져있는 경우라고 볼 수 있겠죠. 이걸 이용하면 이번 집을 G로 칠할 때의 최소값은 이전 집을 R로 칠했을 때의 최소 비용과 B로 칠했을 때의 최소 비용 중 작은 것에 이번 집을 G로 칠하는 데에 드는 비용을 더한 값이 될 것 입니다. 이걸 각 색마다 저장하고 다음 집으로 넘어가서 끝까지 간다면 마지막 집의 색에 따른 최소 비용이 존재할 것입니다. 이 세 값 중 가장 작은 것을 출력하면 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-03-31 18:57:19 |