본문으로 바로가기
글에 개요

백준 알고리즘 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. (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 초256 MB81154553315457.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



댓글을 달아 주세요