[백준 알고리즘] 백준 11048번 이동하기 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 11048번 이동하기 자바(Java)

1) 문제번호 : 11048번

 

2) 문제 출처

www.acmicpc.net/problem/11048

11048번: 이동하기

 

2. 문제

준규는 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)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

 

3. 제약사항

- 

4. 입력

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

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

 

5. 출력

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

 

6. 풀이

- 배열의 값을 입력 받으면서 3방향(왼쪽, 왼쪽 대각선, 위)에서 최대값을 찾아서 배열의 값을 더해준다.

- 그러면 결국엔 배열의 N,M 좌표에는 배열에서의 최대값이 나오게 된다.

 

7. 소스 코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) {		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[][] map = new int[N+1][M+1];
		
		int Max = -1;
		
		//배열 입력
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=M;j++) {
				map[i][j] = sc.nextInt();
				
				//왼쪽, 왼쪽대각선, 위
				Max = Math.max(map[i][j-1], Math.max(map[i-1][j-1], map[i-1][j]));
				map[i][j] += Max;
			}
		}
		
		System.out.println(map[N][M]);
	}
}

 

---