[2096] 내려가기

https://www.acmicpc.net/problem/2096

2096번: 내려가기

처음엔 그래프 탐색으로 접근했지만, DP로 해결한 문제다.

 

풀이

최대 점수를 담는 3칸 크기 배열과 최소 점수를 담는 3칸 크기 배열을 생성한 뒤 매 입력마다 최대, 최소 점수를 누적해 나가면 된다.

단, 갱신되는 주체가 무엇인지를 잘 생각해야한다. 예제를 기준으로 표를 그려봤다.

첫 입력은 당연히 그대로 입력받고 두번째 입력부터 비교를 시작한다. 현재 입력값 기준으로 이전 입력값들의 비교를 통해서 값을 경신해야 한다. 본인은 아무 생각 없이 이전 배열을 기준으로 새로 입력받은 값을 경신해서 오답을 받았다.

마지막 결과인 [12 18 19] 배열 중 가장 큰값이 최댓값이 된다. 최솟값은 반대로 최솟값들로 연상하여 갱신하면 된다.

 

정답 코드