#11048 : 이동하기

풀이방법

사용된 것:

DP 알고리즘

도움이 된 블로그 글

 

2022.01.22

(i, j)에서 (i+1, j+1)까지 대각선으로 이동할 경우,

(i+1, j)를 거쳐 'ㄴ'자로 이동한 경우와 (i, j+1)을 거쳐 'ㄱ'자로 이동한 경우보다 사탕을 더 많이 모으는 것이 불가능하다.

그러므로 대각선으로 이동하는 경우는 배제한다.

 

따라서,

(i, j)까지 이동하면서 모을 수 있는 사탕의 최대 개수는

(i-1, j)까지 이동하면서 모을 수 있는 사탕의 최대 개수에 (i, j)에 있는 사탕의 개수를 더한 것
(i, j-1)까지 이동하면서 모을 수 있는 사탕의 최대 개수에 (i, j)에 있는 사탕의 개수를 더한 것

위의 두 값 중 더 큰 쪽이다.

이 아이디어를 이용하면 (N, M)까지 이동하면서 모을 수 있는 사탕의 최대 개수를 구할 수 있다.

 

이 방법은 두 개의 2차원 배열을 사용해 코드로 구현할 수 있다. 그 과정은 다음과 같다.

 

다음과 같은 입력값이 주어졌다고 하자.

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

 

n = 3, m = 4;

 

int map[][]에는 입력으로 주어진 배열 자체를 저장한다. 단, 가장자리 칸의 예외상황을 손쉽게 처리하기 위하여 가장 윗줄과 가장 왼쪽 줄에 여유 공간을 둔다.

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

map[n+1][m+1]의 모습

 

int max[][]에는 각 칸까지 진행하면서 모을 수 있는 사탕의 최대 개수를 저장한다.

max 또한 map처럼 가장 윗줄과 가장 왼쪽 줄에 여유 공간을 둔다.

즉, max[i][j]의 값은 (i, j)까지 진행하면서 모을 수 있는 사탕의 최대 개수이다.

 

위에서 설명한 아이디어를 활용하여 max[2][2]를 구해보자.

max[2][2]는

(1, 2)까지 이동하면서 모을 수 있는 사탕의 최대 개수에 (2, 2)에 있는 사탕의 개수를 더한 것
(2, 1)까지 이동하면서 모을 수 있는 사탕의 최대 개수에 (2, 2)에 있는 사탕의 개수를 더한 것

위의 둘 중 더 큰 쪽이다.

 

즉,

max[1][2] + map[2][2]
max[2][1] + map[2][2]

위의 둘 중 더 큰 쪽을 골라 max[2][2]에 저장하면 된다.

 

max[1][1]부터 max[n][m]까지 모든 칸을 이러한 방법으로 채운다.

max[n][m]의 값이 이 문제의 정답이다.

 

코드

Java(2022.01.22)

import java.util.Scanner;

public class Main {

	public static void main(String[] args){
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		//각 구역의 사탕 개수를 저장할 배열.
		int[][] map = new int[n+1][m+1];
		//최대 개수 저장용 배열. max[i][j]는 (i,j)까지 오면서 모을 수 있는 사탕의 최대 개수
		int[][] max = new int[n+1][m+1];
		
		for(int i = 1; i<n+1; i++) {
			for(int j = 1; j<m+1; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		for(int i = 1; i<n+1; i++) {
			for(int j = 1; j<m+1; j++) {
				max[i][j]= Math.max(max[i-1][j] + map[i][j], max[i][j-1] + map[i][j]);
			}
		}
		
		System.out.print(max[n][m]);
		
		sc.close();
	}
	
}