5. RGB 거리 - 다이나믹 프로그래밍 문제 (Baek-Joon 사이트 1149번)

1. 문제

이 문제는 먼저 반복문 방식으로 다이나믹 프로그래밍을 작성했다.

하지만 문제에서 주어진 기본 테스트는 맞게 나왔는데 틀렸다.

그래서 다른 사람의 코드를 참고했다.

이 사람은 재귀 방식으로 풀었다.

하지만 궁금한 것은 분명 문제에서 i-1, i, i+1 모두 이웃이기에 같은 색이되면 안된다 라고 나는 이해했는데

이 사람의 코드를 보니 단순히 인접하는 집만 색만 다르면 된다는 식의 코드이다.

내가 잘못이해한 것이겠지. 그래도 이 문제 역시 DP를 재귀적으로 풀어내는게 아주 깔끔하다.

또한 배운점.

#include<algorithm> 함수 속의 min 함수

min 함수는 argument가 3개 이상일 경우, 그 겉에 대괄호 { } 로 묶어준다.

논리 흐름

(1) 맨 처음 집을 각각 빨간색, 초록색, 파란색으로 칠한다.

(2) 이전 집의 색이 아닌 색으로 다음 집을 칠한다.

(3) (1) ~ (2) 를 끝날 때까지 반복한다.

(4) 모든 경우의 길 중 가장 비용이 싼 길을 선택한다.

2. 코드

2-1) 메인 코드

2-2) 핵심 코드

2-3) 출력

2-4) 결과

3. 정리

 정리로는 재귀적 방식은 언제나 한 순간에 하나의 테스트를 생각하자.

 그리고 가능하다면 꼬리 재귀로 바뀔 수 있는 문제인지 또 생각해보자.

 실력자는 언제나 한 걸음씩 전진하고, 허접은 문제를 한 방에 풀어내려 한다. - 난 가우스가 아니다.