[백준 11048 / 이동하기 / JAVA]

https://www.acmicpc.net/problem/11048

11048번: 이동하기

 

문제 접근

N, M 좌표까지 가는 모든 경우의 수를 다 탐색해서 최대값을 구하였는데 시간초과가 뜨더라

 

시간을 단축시키기 위해선 각 좌표마다 그 좌표가 가질 수 있는 최대값을 저장해놓은 것이라고 한다.

 

사람이 움직일 수 있는 방향은 오른쪽, 아래, 오른쪽 아래 대각이니까 현재 서 있는 좌표가 최대값을 가지려면

현재 서 있는 좌표의 사탕 갯수 + 위, 왼쪽, 왼쪽 위 대각 (현재 서 있는 좌표로 오기위해 지나올 수 있는 길들) 중 가장 많은 사탕 갯수를 더해준다 (그 길을 통해서 왔다는 뜻)

이렇게 연산해 나가면 모든 좌표에 그 경로로 갔을 때 최대 사탕 갯수가 저장되어있다.

이후 마지막 좌표까지 계산을 마치고 출력

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] maze = new int[N+1][M+1];
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=M; j++) {
				maze[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=M; j++) {
				maze[i][j] += Math.max(maze[i-1][j], Math.max(maze[i-1][j-1], maze[i][j-1]));
			}
		}
		System.out.println(maze[N][M]);
	}
}

 

시간 초과 코드

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

public class Main {
	static int[][] maze;
	static int N;
	static int M;
	static int candy = 0;
	static int sum = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		maze = new int[N+1][M+1];
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=M; j++) {
				maze[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		dfs(1, 1);
		System.out.println(candy);
	}
	
	public static void dfs(int i, int j) { 
		sum += maze[i][j];
		
		if(i == N && j == M) candy = Math.max(candy, sum);
		
		
		// 하
		if(i+1 <= N) dfs(i+1, j);
		
		// 우
		if(j+1 <= M) dfs(i, j+1);
		
		// 대각
		if(i+1 <= N && j+1 <= M) dfs(i+1, j+1);
		
		sum -= maze[i][j];
	}
}