[랜덤 마라톤] 진우의 달 여행 (Small)(17484)

1. 문제 풀이 아이디어

• 각 위치에서 3가지 경로로 이동했을 때의 최소값을 저장하며 계산하면 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int n = Integer.parseInt(stringTokenizer.nextToken());
        int m = Integer.parseInt(stringTokenizer.nextToken());
        int[][][] map = new int[n][m][4];
        for (int i = 0; i < n; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j][0] = Integer.parseInt(stringTokenizer.nextToken());
                if (i == 0) {
                    for (int k = 1; k < 4; k++) {
                        map[i][j][k] = map[i][j][0];
                    }
                    continue;
                }
                if (j - 1 < 0)
                    map[i][j][1] = Integer.MAX_VALUE;
                else
                    map[i][j][1] = map[i][j][0] + Math.min(map[i - 1][j - 1][2], map[i - 1][j - 1][3]);
                map[i][j][2] = map[i][j][0] + Math.min(map[i - 1][j][1], map[i - 1][j][3]);
                if (j + 1 >= m)
                    map[i][j][3] = Integer.MAX_VALUE;
                else
                    map[i][j][3] = map[i][j][0] + Math.min(map[i - 1][j + 1][1], map[i - 1][j + 1][2]);
            }
        }
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < 4; j++) {
                result = Math.min(result, map[n - 1][i][j]);
            }
        }
        System.out.println(result);
        bufferedReader.close();
    }
}

3. 정리

• 각 위치에서 기본 소비 연료와 3가지 경로로 이동했을 때의 최소 소비 연료를 저장하기 위해 크기가 N x M x 4인 배열을 정의한다.

• i가 0일 때는 출발점이므로 3가지 경로의 값에 모두 기본 소비 연료 값을 저장한다.

• 각 위치에서 경로를 계산할 때, 이전 위치가 유효하지 않은 경우 정수 최대값을 저장하고, 유효한 경우 다른 경로 중 최소값을 현재 경로의 소비 연료 값에 더해 저장한다.

• 모든 경로 계산이 끝난 후, 마지막 행에서 가장 작은 값을 찾아 문제를 해결한다.