BaekJoon 1149 RGB 거리
2019. 1. 14.
Link https://www.acmicpc.net/problem/1149 소스결과 2012 KB / 0 ms 출처 Backjoon 언어 C++ 17 분류 다이나믹프로그래밍 설명 이웃한 집과 같은색으로 칠하지 않으면서 모든 집을 칠할 때 드는 비용의 최솟값을 출력하는 문제 이전 집의 색을 기억해서 같은 색이면 그 색을 제외하고 최솟값을 구해 마지막까지 칠하는 경우 모든 경우에서 최솟값을 선택하는 그리디 알고리즘을 적용시키면 문제의 정답이 나오지는 않는다. 같은 값이 존재하는 경우 위치에 따라 다른 결과 값이 나올 수 있다는 점을 유의해야한다. 또한 매번 최선의 선택이 정답이 되지 않기 때문에 모든 경우에 대해서 검사를 해야 한다. DFS로 풀어나가면 시간 초과가 나온다. 점화식은 첫 번쨰 경우를 제외하고..
