BOJ 11048_이동하기

이동하기

문제

준규는 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

 

준규는 어쩌다가 미로에 갇힌 걸까 

아무튼 DP로 풀어야 한다. 

마침 노트해놓은 게 있는데

절대 타자치기 귀찮은 게 아니고

아무튼 저런 식을 뽑을 수가 있다는 거다 

이걸 코드로 구현하면 다음과 같다 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_11048 {
	// 이동하기, DP
	static int[][] board;
	
	public static void main(String[] args) {
		set();
		System.out.println(calc());
	}
	
	static void set() {
		Scanner sc = new Scanner(System.in);
		board = new int[sc.nextInt()][sc.nextInt()];
		
		for(int i = 0; i<board.length; i++) {
			for(int j = 0; j<board[0].length; j++) {
				board[i][j] = sc.nextInt();
			} // for j
		} // for i
	} // void set
	
	static int calc() {
		int[] dx = {-1, 0, -1}; // 왼쪽, 위, 대각선 왼쪽 위// c
		int[] dy = {0, -1, -1};  // r
		
		for(int i = 0; i<board.length; i++) {
			for(int j = 0; j<board[0].length; j++) { // 주어진 배열의 한 자리씩 탐색한다.
				
				Queue<Integer> minis = new LinkedList<>();
				for(int k = 0; k<dx.length; k++) {
					try {
						minis.add(board[i+dy[k]][j+dx[k]]); // 무조건 1개 아니면 3개 들어감
					}catch(IndexOutOfBoundsException e) {
						// do nothing
					}
					
				} // for int k
				switch(minis.size()) {
				case 0 : // [0][0]
					break;
				case 1 : // max를 돌릴 필요가 없다. 
					board[i][j] = minis.poll() + board[i][j];
					break;
				case 3 : 
					board[i][j] = max(minis.poll(), minis.poll(), minis.poll()) + board[i][j];
					break;
				}
			} // for int j
		} // for int i
		return board[board.length-1][board[0].length-1];
	} // int calc
	
	static int max(int a, int b, int c) {
		int max = a;
		if(b>max) max = b;
		if(c>max) max = c;
		return max;
	} // int max
}

그러면 맞는다 

메모리가 음 ? 스럽지만

기죽으면 안 된다 맞았으면 장땡