[백준 1149 C++] RGB 거리

오늘은 백준(BOJ) 1149번 RGB 거리 문제에 대해 다뤄볼 예정이다.

RGB 거리 문제 링크 (백준(BOJ) 1149번 문제): https://www.acmicpc.net/problem/1149 

1149번: RGB거리

문제 설명 

백준 1149번 RGB 거리 문제는 N개의 집을 색칠하려고 하는데 현재 집이 i 번째라고 했을 때 이웃 간( i -1 또는 i + 1)의 집과 색깔이 다르면서 최소 값을 구하는 문제이다. 

문제 풀이 

백준 1149번 RGB 거리 문제의 제약 조건을 통해, 얻을 수 있는 정보는 현재 집이 이전 집의 색깔과 다르면서 최소 값을 구해주는 것이다. 단, 이 문제는 시간이 0.5초 내에 해결되어야 하므로 DP(Dynamic Progrmming) 알고리즘을 사용하여 해결해주어야 한다. 

(DP의 장점: 특정 케이스의 결과 값을 저장하고 있어 이미 계산된 경우 반복적으로 계산하지 않아도 된다.) 

 

이를 소스코드로 나타내면 아래와 같다.