백준 11048. 이동하기

🅰 백준 11048. 이동하기

11048번: 이동하기

✏️ 문제 풀이

• dp로 생각해보면 한 좌표에서 올 수 있는 값은 위, 왼쪽, 왼쪽 위 대각선 3가지 이다. 
• 가져올 수 있는 사탕의 최대값을 구해야 하기 때문에 이전 3가지 값 중 최적의 값을 가져오면 된다.
• 하지만 첫째줄 행, 첫째줄 열은 대각선탐색, 위, 왼쪽 탐색등에 제약이 있으므로 basevalue로 값을 넣어주고 나머지 행에 대해서 이전 값 중 최적값을 구해서 마지막 map[N][M]이 정답이 된다.

✏️ 소스코드

package dp;

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

public class Main_실버1_11048_이동하기 {
	static int N, M;
	static int[][] map, candy;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N + 1][M + 1];
		int cnt = 0;
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for (int i = 2; i <= N; i++) {	// 첫째줄 행, 열은 이전값 탐색이 안되므로 기본 값 설정, base value
			map[i][1] = map[i][1] + map[i - 1][1];
		}
		for (int i = 2; i <= M; i++) {
			map[1][i] = map[1][i] + map[1][i - 1];
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (i == 1 || j == 1) continue;
				map[i][j] = Math.max(Math.max(map[i - 1][j], map[i][j - 1]), map[i - 1][j - 1])+map[i][j]; // 이전값 중 최적의 값을 가져옴
			}
		}
		System.out.println(map[N][M]);
	}
}

 

✅ 후기

• dfs 시간초과, 배열 전체를 탐색해서 중복되는 값들도 계속 탐색함
• 전체를 탐색하는 것이 아닌 2중 for문을 이용해서 이전 가능한 값 중 최적의 값을 가져옴