1149

간단한 동적계획법 문제이다. 이 문제는 아주 예전부터 백준 알고리즘에서 동적계획법으로 문제 분류가 되었다고 한다. 그 만큼 아주 괜찮은 문제라는 것... 아래의 그림을 보도록 하자. N번째 집을 R로 칠했을때의 최대값은 그 이전인 N-1을 G로 칠했을때와 B로 칠했을때의 값중 최대값을 골라서 N번째 집을 R로 칠했을 때의 비용을 합산한 것이다. 그러면 N-1 번째 집을 G 또는 B로 칠했을때의 최대값은 어떻게 구하는가? 또 N-2번째에서의 최대값을 구해봐야하고 이러면 또 N-3 또 N-4 또 N-5 쭉쭉쭉 이어져서 1번째까지 내려가게 된다. 재귀함수로 분기를 하고, 같은 계산시 이득을 볼수 있도록 배열로 저장해둔 값을 적용한다. 코드는 다음과 같다. #include #include enum RGB { R..