[백준 BOJ] 1149 RGB거리

[백준 BOJ] 1149 RGB거리

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다..

문제로 이동할려면 여기를 클릭하세요.

풀이

  • DP를 자신의 색깔이 아닌 다른 두 색깔을 재귀호출하고 그 중 작은 값을 리턴하는 방식으로 구현합니다.
  • cache 배열을 이용해 메모이제이션을 해줘 시간초과를 방지해줍니다.

예제

1
2
3
4
5
6
7

입력

3
26 40 83
49 60 57
13 89 99

노트북

코드

comments powered by Disqus