(JAVA) 백준 2096번 : 내려가기 --- [슬라이딩 윈도우, DP]

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

2096번: 내려가기

 

 

안녕하세요.

 

이 문제는 Sliding Window 와 DP를 활용했습니다.

 

 

그냥 DP만 사용해도 되지만, 문제 조건을 보면

 

 

 

1초와 메모리 제한이 4MB 이기 때문에 모든 숫자를 배열로 담고 활용할 수 없습니다.

 

그래서 슬라이딩 윈도우 를 사용해야 합니다.

 

 

근데 문제를 보면

 

한 줄씩 확인해서 DP로 최댓값, 최솟값을 구하기만 하면

 

굳이 이전 값을 알 필요가 없습니다.

 

 

즉, DP[i][k] 2차원 배열이 있다고 할 때 (i = 해당 번 째 줄, k = 왼쪽부터 해당 번 째 칸)

 

직접 그렸습니다..

 

최댓값 DP[i][0] = Math.max(DP[i - 1][0], DP[i - 1][1]) + Map[i][0]

최댓값 DP[i][1] = Math.max(DP[i - 1][0], DP[i - 1][1], DP[i - 1][2]) + Map[i][1]

최댓값 DP[i][2] = Math.max(DP[i - 1][1], DP[i - 1][2]) + Map[i][2]

*** 최솟값은 Math.min 으로 구하면 됩니다.

 

 

내려갈 수 있는 경우 중에서 최대인 값(또는 최소인 값) 을 찾아 내려간 다음의 수와 더해주면 됩니다.

 

이를 길이가 3인 1차원 배열을 여러 개 만들어서 한 층씩 탐색하고, 결과만 집어넣으면 되죠.

 

 

이해되셨나요?

 

소스코드를 보면 더욱 쉽게 이해하실 수 있습니다.

 

 

 

감사합니다!

 

 

소스코드

---