백준 17391 - 무한부스터

Java

17391 번 - 무한부스터

문제

접근 방법

코드

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

public class Main {
	static int n, m, result;
	static int[][] map;
	static int[][] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	map = new int[n][m];
    	dp = new int[n][m];

    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < m; j++) {
    			map[i][j] = stoi(stk.nextToken());
    		}
    		Arrays.fill(dp[i], 10000000);
    	}
    	dp[0][0] = 0;

    	for(int i = 0; i < n; i++) {
    		for(int j = 0; j < m; j++) {
    			if(i == 0 && j == 0)
    				continue;
    			// 가로 탐색
    			for(int k = j - 1; k >= 0; k--) {
    				if(map[i][k] >= j - k) {
    					dp[i][j] = Math.min(dp[i][j], dp[i][k] + 1);
    				}
    			}
    			// 세로 탐색
    			for(int k = i - 1; k >= 0; k--) {
    				if(map[k][j] >= i - k) {
    					dp[i][j] = Math.min(dp[i][j], dp[k][j] + 1);
    				}
    			}
    		}
    	}
    	System.out.println(dp[n - 1][m - 1]);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

전형적인 dp 문제

개선할 점