11491 [백준 / BOJ] RGB거리 - 1149 (Java) 문제 : https://www.acmicpc.net/problem/1149 서로 인접한 집끼리 서로 다른 색(3가지 색을 사용할 수 있다)으로 칠할 때, 최소 비용을 구하는 문제이다. 입력첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. 풀이나이브하게 모든 조합을 모두 탐색한다고 생각해보면 O(3^N)의 복잡도를 가진다. N은 최대 1,000이므로 모든 조합을 탐색하는 것은 불가능한 것을 알 수 있다. 해당 문제는 DP를 활용하여 해결할 수 있다. i 번째 집을 칠할 때, i-1번째 집까지 칠한 상태를 참고하는 방식이다... 2025. 1. 23. 이전 1 다음
