[백준 11048] 이동하기 (DP, 최댓값,최솟값 구하는 문제로 확장)

글에 개요

백준 알고리즘 11048번 "이동하기" 문제입니다.

DP를 활용하는 기본적인 문제입니다.

해당 문제는 이동하면서 주울 수 있는 캔디의 최댓값을 구하는 문제이지만 캔디의 최솟값을 구하는 문제로도 확장해서 해결해 보겠습니다.

두 가지 방법으로 해결하겠습니다. 하지만, 핵심은 같습니다!!!

최댓값 구하는 방법은 [해결방법1번]으로 구하는게 좋습니다!!

최솟값 구하는 방법은 [최솟값 해결방법2번]으로 구하는게 깔끔합니다!!

[백준 11048] 이동하기 : https://www.acmicpc.net/problem/11048

핵심 내용

1. 시간 초과 이슈를 줄이기 위해 DP를 활용하자!!
2. (1,0), (0,1), (1,1) 방향으로 이동할 수 있지만 점화식을 세울 때 생각해보면, 캔디 숫자는 음수가 될 수 없으므로 (1,1) 즉 대각선 방향으로 가는 것은 최댓값이 될 수 없으므로 제외해도 무방합니다.
3. 아래쪽과 오른쪽으로 이동했을 때 최댓값이 될 수 있는 지를 고민하면 되는 문제입니다.
1. 즉, candyCntMap[i][j] += Math.max(candyCntMap[i-1][j], candyCntMap[i][j-1]) + inputAry[i][j];

해결 방법

1. 오른쪽과 아래쪽 값만 비교하여 큰 쪽으로 이동하면 됩니다!!!

해결한 코드

[해결방법 1]

[해결방법 2]

[최솟값을 구하는 문제로 바꿔본다!!]

핵심 내용

1. (1,0), (0,1), (1,1) 방향을 모두 고려해줘야 된다.
2. candyCntMap의 1열과 1행의 값들을 초기화 시켜줘야된다.

해결 방법

1. [해결방법 1]
1. [해결방법 1] 행이 1일 때, 열이 1일 때 0이 아닌 inputAry의 값으로 초기화 해줘야됩니다.
2. i = 2, j = 2부터 탐색을 시작해야 됩니다. i=1,j=1부터 시작할 경우 초기화하지 않은 0번 행과 0번 열에 담긴 0과 비교가 되기 때문에 안된다.
3. CandyCntMap[i][j] += Math.min(candyCntMap[i-1][j-1], Math.min(candyCntMap[i][j-1], candyCntMap[i-1][j])) + inputAry[i][j];
2. [해결방법 2]
1. 3방향 코드 탐색 코드로 최댓값 구하는 코드에서 부등호만 바꿔주면 된다.
2. CandyCntMap의 초기값을 모두 Integer.MAX_VALUE로 바꿔준다!!!!

해결한 코드

[해결방법1]

[해결방법2]

백준 내용 참고

이동하기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	8115	4553	3154	57.096%

문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최대값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

예제 입력 1 

3 4
1 2 3 4
0 0 0 5
9 8 7 6

예제 출력 1 

31

예제 입력 2 

3 3
1 0 0
0 1 0
0 0 1

예제 출력 2 

3

예제 입력 3 

4 3
1 2 3
6 5 4
7 8 9
12 11 10

예제 출력 3 

47