#2096 내려가기

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

2096번: 내려가기

 

별모양이 3개의 칸 중 하나를 선택하며 밑으로 계속 내려가면서 거쳐간 경로의 최솟값 최댓값을 구하는 문제이다.

dp를 이용한 점화식을 구하여 해결하는 문제인데 처음에 dp의 배열을 dp[100001][3]과 같이 지정을 하면서 메모리의 초과가 일어났다. 하지만 dp를 dp[3]으로 지정하고 입력값만을 통해서도 계속해서 dp값을 갱신하면서 마지막 최댓값 최솟값을 구할 수 있다.

 

점화식 알고리즘은 다음과 같다.

 

현재 dp[0~2]= 전단계의 dp[0~2]중 최대 or 최솟값 + 현재 방문한 노드값(arr[0~2])

 

소스코드