DP
BOJ 1149 RGB거리 [Java]
BOJ 1149 RGB거리 1. 문제 링크 https://www.acmicpc.net/problem/1149 2. 문제 해설 DP문제를 풀 때는 개인적으로 점화식을 세우는 것이 절반 이상이라고 생각한다. 일단 문제를 이해해보자. 문제를 읽어보면 각 집마다 빨강, 초록, 파랑 3가지 색 중 1개를 선택해서 칠할 수 있다. 또 추가적인 조건이 있는데 아래와 같다. - 1번 집의 색은 2번 집의 색과 같지 않아야 한다. - N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. - i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 복잡하게 쓰여있지만 결국 말하고자하는 바는 이웃한 집과는 색이 달라야한다는 것이다. 구하고자 하는 정답은 위 조건을 만족하면서 모든 집을 칠하..