백준 RGB거리1 [백준 1149번] RGB 거리 풀이 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 집 N개를 각각 빨강(r), 초록(g), 파랑(b)으로 칠할 때의 비용이 주어진다. i번째 집은 i-1 번째 집과 다른 색으로 칠해져야 한다. N개의 집에 대하여 칠할 수 있는 모든 조합을 탐색하면, //R로 시작하는 경우 R / G / \ / B R ... \ R \ / B \ G 경우의 수가 2의 거듭제곱으로 늘어 시간 복잡도는 3 * 2^(N-1) 이 된다. 해당 방법은 시간 초과가 예상되므로, 다이내믹 프로그래밍(dp) 점화식을 세워.. 2021. 10. 11. 이전 1 다음