백준 - 11048번 이동하기

또여·2022년 1월 21일
0

백준

목록 보기
15/17

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

접근법

기본적인 DP 풀이법
핵심은 DP[nextX][nextY] < DP[x][y] + Array[nextX][nextY]를 판단해서 더 큰 경우 DP배열을 갱신해주고
출력할 때는 마지막 (N-1, M-1)값을 출력해줌

소스

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

public class Main {
	static int N, M;
	static int[][] Array;
	static int[][] DP;
	static int[][] dir = {{1,0},{0,1},{1,1}};
	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());
		
		Array = new int[N][M];
		DP = new int[N][M];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < M; j++) {
				Array[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		DP[0][0] = Array[0][0];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				for(int k = 0; k < 3; k++) {
					int nextX = i + dir[k][0];
					int nextY = j + dir[k][1];
					
					if(nextX >= N || nextY >= M) continue;
					
					if(DP[i][j] + Array[nextX][nextY] > DP[nextX][nextY]) {
						DP[nextX][nextY] = DP[i][j] + Array[nextX][nextY]; 
					}
				}
			}
		}
		System.out.println(DP[N-1][M-1]);

	}

}
profile
기록 열심히하는 개발자인척

0개의 댓글