BOJ) 이동하기

이동하기

11048번: 이동하기

풀이

 

미로에 같힌 준규가 각 방에 놓여있는 사탕을 주워먹으면서 갈 때, 먹을 수 있는 사탕의 최대 갯수를 구하는 문제다.

이 문제는 언젠가 풀었던 것 같다. 아마 프로그래머스 문제 중 하나이지 않을까 싶다.

아무튼, dp를 이용해서 문제를 풀었다.

 

맵의 처음부터 x축을 순회하면서 좌측과 상단 중 사탕이 더 많은 갯수를 더해가면서 마지막 위치에 도달하게 설정했다.

이후, n, m의 dp값을 출력해서 답을 쉽게 구할 수 있었다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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[][] map = 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        br.close();
        solution(n,m,map);
    }

    private static void solution(int n, int m, int[][] map) {
        int dp[][] = new int[n+1][m+1];
        for(int y=1; y<=n; y++) {
            for(int x=1; x<=m; x++) {
                dp[y][x] = map[y][x] + Math.max(dp[y-1][x], dp[y][x-1]);
            }
        }
        System.out.println(dp[n][m]);
    }
}