Baekjoon 11048 이동하기 JAVA

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

11048번: 이동하기

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2011048

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 map가 주어졌을 때 1,1에서 N, M까지 이동하면서 사탕을 얻는 최대 개수를 출력하는 문제다

이동은 오른쪽 아래 오른쪽 대각선 아래로 이동 가능하다.

​

오랜만에 dp 문제를 풀어보려고 dp 문제를 찾아보다가 실버 1이길래 풀어봤는데

너무 쉽게 풀었던 거 같다.

​

현재 값은 이동 가능한 방향 반대 방향의 값과 현재 자신의 값중 큰값을 계속 dp 배열에 저장하면서 진행하면

되는데 그냥 dp 배열을 하나 두고 값을 입력받으면서 비교했다 어차피

비교하는 부분은 왼쪽, 위, 왼쪽 위 대각선 부분인데 해당 부분들은 이미 입력되어 있기 때문

점화식은 아래와 같다.

n 은 현재 입력받은 값

dp[i][j] = Math.max(dp[i-1][j-1]+n, Math.max(dp[i-1][j] + n, dp[i][j-1] + n))