[BOJ] 백준 2096 내려가기 (JAVA)

다이나믹 프로그래밍!

📑 문제

백준 2096 내려가기

---

🌱 아이디어

메모리 제한 4MB이다, 즉 메모리 초과된다면 불필요한 메모리는 줄여야 한다.

 

처음 풀었을 때 N = 100,000까지 모든 입력을 배열에 받고 저장했다... 그러다 보니 메모리 초과가 나서 틀렸다

이 문제는 사실 입력을 저장할 필요 없다 입력되면 -> dp로 처리한다 이를 N번 반복하면 된다

 

이 문제는 다이내믹 프로그래밍 알고리즘을 사용한다 즉 우리는 3가지 경우에 대한 점화식을 세우면 된다!

j = 1

 

j = 2

 

j = 3

 

최댓값 구하는 경우

j =1 , 점화식 = dp1[1] = max(dp1[1], dp1[2])+ n1

j =3 , 점화식 = dp1[3] = max(dp1[3], dp1[2])+ n3

j =2 , 점화식 = dp1[2] = max(dp[1] , max(dp[2], dp[3])+ n2

내려갈 수 있는(선택 가능한) 숫자 중 가장 큰 값을 고르고 입력된 값을 더해준다. 그 후 메모이제이션기법으로

계속 계산값을 저장하면서 푼다!  물론 최솟값은 Math.min을 사용하면 된다.

---

🌱 코드 및 풀이

위에서 설명한 것처럼 구현할 때는 어려울 것은 없다. 하지만 주의해야 하는 부분이 있다.

 

dp1[0] = Math.max(dp1[0], dp1[1]) + n1;

dp1[2] = Math.max(dp1[1], dp1[2]) + n3;

dp1[1] = Math.max(dp1[1], Math.max(tmp1, tmp2)) + n2;

 

모든 계산은 초기값을 기준으로 계산해야 하는데 이 경우는 dp1[0], dp1[2] 계산되면 dp1[1]은 초기값을 사용하지 못한다.

이를 해결하려면 초기값을 변수에 담아야 한다.

int tmp1 = dp1[0];

int tmp2 = dp1[2];

먼저 변경될 dp1배열에 들어있는 초기값을 변수에 담고 dp1[1] 계산할 때 사용한다면 위 문제는 해결된다.

---

🌱 느낀 점

잘 푼것 같다 ㅎㅎ

오랜만에 다이나믹 프로그래밍을 이용해 봤는데 재미있었다, 항상 하는 말이지만 점화식을 생각해 내고 구현하는 과정이

가장 어려운 것 같다. 하지만 이 문제는 패턴을 먼저 알려줘서 쉽게 푼 것 같다

가장 어렵다 생각한 것을 풀게 됐을 때가 가장 재미있는 것 같다 ㅎㅎ