-
https://www.acmicpc.net/problem/11048
https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2011048
해당 문제는 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))
728x90'알고리즘 > Baekjoon' 카테고리의 다른 글
Baekjoon 4963 섬의 개수 JAVA (0) 2021.11.14 Baekjoon 2174 로봇 시뮬레이션 JAVA (0) 2021.11.14 Baekjoon 13023 ABCDE JAVA (0) 2021.11.14 Baekjoon 3190 뱀 JAVA (0) 2021.11.14 Baekjoon 7562 나이트의 이동 JAVA (0) 2021.11.14 댓글