https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 잘못 생각하면 그리디 알고리즘을 떠올릴 수 있다. 1번째 집부터 접근하여 3가지 색 중 가장 비용이 적은 색으로 칠하고, 2번째 집에 접근하여 1번째 집이 사용한 색을 제외하고 비용이 적은 색으로 칠하는 방식이다. 그러나 이는 잘못된 방법이다. 반례는 다음과 같다. 각 집이 빨간색, 초록색, 파란색으로 집을 칠하는 비용이 아래와 같다. 1번 집 1 100 103 2번 집 1 ..