[Backjoon] 11048번 문제 - 이동하기

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

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

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

풀이

재귀로 풀었다가 시간초과 걸려서 다시 문제를 풀었다.

백준 문제풀이는 시간초과가 있으니 입력값이 적당히 크다 싶으면 반복문으로 풀기 바란다.

우선 누적된 사탕의 값을 저장하기위한 2차원 배열 comp를 생성해준다.

그리고 반복문을 순환하며 사탕이 놓여져 있는 값을 누적해주고 N,M에 도달하면 해당 위치의 값을 출력하고 종료한다.

여기서 중요한점은 조건문 처리이다.

0,0 좌표에서 목표까지 도달하기 위해, 왼쪽에서 오른쪽, 아래에서 위로, 2방향에서 이동하는 것이 가능하다.

따라서 이 둘중 어느값을 누적하는것이 더 큰값을 가질수 있으냐를 판별하는것이 첫번째이다.

두번째로 x,y 좌표값이 0일때는 1방향에서 접근하므로 이를 처리해줘야한다.

마지막으로 0,0의 comp값은 초기 array의 0,0값과 동일하다는 것이다.

이러한 조건 처리를 해준다면 올바른 결과값을 얻을 수 있다.

import java.util.Scanner;
 
/**
 * Created by homr on 2017. 6. 27..
 */
public class Main {
 
 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] arr = new int[N][M];
        int[][] comp = new int[N][M];
 
        for(int i =0; i<N; i++){
            for(int j =0; j<M; j++){
                arr[i][j] = sc.nextInt();
            }
        }
 
        for(int i=0; i<N; i++){
            for(int j =0; j<M; j++){
                if(i==0&&j==0){
                    comp[i][j]=arr[i][j];
                }else if(i==0){
                    comp[i][j]=arr[i][j]+comp[i][j-1];
                }else if(j==0){
                    comp[i][j]=arr[i][j]+comp[i-1][j];
                }else{
                    int candy1 = comp[i-1][j];
                    int candy2 = comp[i][j-1];
                    comp[i][j] = candy1>candy2 ? arr[i][j]+candy1 : arr[i][j]+candy2;                    
                }
            }
        }
 
        System.out.println(comp[N-1][M-1]);
 
    }
 
}