codingtest

20293번 - 연료가 부족해

2025-02-17
4분 분량
JAVA백준

문제 링크

문제 풀이 시간 : 2시간

문제 풀이 :

처음에는 간단한 dfs 문제라고 생각하고 dfs로 코드를 짰다

초기 위치에서 가지고 있는 연료(have)와 필요한 연료(need)를 둘 다 0으로 초기화하고,

dfs로 탐색하면서 각 위치에 따라 have가 있다면 다음 위치로 이동하며 have를 1 차감하고,

have가 0이라면 need를 1 증가하며 이동했다.

java
public static void dfs(int x, int y, int have, int need) { //x좌표, y좌표, 가지고 있는 연료, 필요한 연료
        if (x == r && y == c) { //목적지에서 필요한 연료 계산
            min = Math.min(need, min);
            return;
        }
        if (arr[x][y] != 0) { //현재 위치가 충전소라면 연료 충전
            have += arr[x][y];
        }
        for (int i = 0; i < 2; i++) {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];

            if (check(dx, dy)) { //지도를 벗어나지 않는지
                return;
            }

            if (have > 0) { //연료가 있다면
                dfs(dx, dy, have - 1, need); //연료 차감
            } else { //연료가 없으며
                dfs(dx, dy, have, need + 1); //필요한 연료 증가
            }
        }
    }

그리고 마지막 r,c 위치에서 need의 수를 출력하면 최초에 필요한 연료의 크기를 구할 수 있다.

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

class Main{
    public static int r,c,n;
    public static int[][] arr;

    public static int[][] dir = {{0, 1}, {1, 0}};
    public static int min = Integer.MAX_VALUE;

    public static boolean check(int a, int b) {
        return a < 1 || a > r || b < 1 || b > c;
    }

    public static void dfs(int x, int y, int have, int need) { //x좌표, y좌표, 가지고 있는 연료, 필요한 연료
        if (x == r && y == c) { //목적지에서 필요한 연료 계산
            min = Math.min(need, min);
            return;
        }
        if (arr[x][y] != 0) { //현재 위치가 충전소라면 연료 충전
            have += arr[x][y];
        }
        for (int i = 0; i < 2; i++) {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];

            if (check(dx, dy)) { //지도를 벗어나지 않는지
                return;
            }

            if (have > 0) { //연료가 있다면
                dfs(dx, dy, have - 1, need); //연료 차감
            } else { //연료가 없으며
                dfs(dx, dy, have, need + 1); //필요한 연료 증가
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(br.readLine());

        arr = new int[r + 2][c + 2];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
        }

        dfs(1, 1, 0, 0);
        System.out.println(min);
    }
}

하지만 이렇게 하면 1%에서 시간초과가 나온다.

아무리 생각해도 방법을 모르겠어서

결국 다른사람들의 코드를 참고했다.

이 문제는 dp와 이분탐색을 사용해서 풀어야하는 문제이다.

  • 이동은 아래, 오른쪽 두가지만 존재하기 때문에 1,1에서 r,c로 이동할 때 필요한 최대 연료는 r+c-2이다.
  • 초기 연료 f를 1,1과 r+c-2 사이에서 이분탐색하며 탐색한다.
  • find(f)를 이용해서 f라는 연료를 통해 1,1에서 r,c로 이동할 수 있는지 확인한다.
java
int s = 1, e = r + c - 2;
while (s <= e) {
    int mid = (s + e) / 2;
    
    if (find(mid)) {
        e = mid - 1;
    } else {
        s = mid + 1;
    }
}

  • dp배열에는 i번째 위치에서의 연료의 양이 저장되어 있다.
  • 각 위치는 시작위치, 충전소의 위치, 도착위치가 있다. (즉, dp 배열의 크기는 n+2)
  • 그 후 각 위치에서 이전 위치에서 현재 위치로 이동할 수 있는지 확인한다.

java
public static boolean find(int f) {
    int[] dp = new int[n + 2];
    
    Arrays.fill(dp, -1);
    dp[0] = f; //초기 위치 연료량 설정
    fuels[0][2] = f; //초기 위치 연료량 설정
    
    for (int i = 1; i < n + 2; i++) {
        for (int j = 0; j < i; j++) {
            if (fuels[j][0] > fuels[i][0] || fuels[j][1] > fuels[i][1]) { //j위치에서 i위치로 이동할 수 없음
                continue;
            }
            
            if (dp[j] < dist(j, i)) { //이동거리보다 연료량이 적음
                continue;
            }
            
            //dp배열 최대크기로 설정
            dp[i] = Math.max(dp[i], dp[j] - dist(j, i) + fuels[i][2]); 
        }
    }
    
    //도착점의 dp 배열 값이 0이상이라면 true 반환
    return dp[n + 1] >= 0;
}

전체 코드

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

class Main {
    public static int r, c, n;
    public static int[][] fuels;

    public static int dist(int i, int j) {
        return fuels[j][0] + fuels[j][1] - fuels[i][0] - fuels[i][1];
    }

    public static boolean find(int f) {
        int[] dp = new int[n + 2];

        Arrays.fill(dp, -1);
        dp[0] = f;
        fuels[0][2] = f;

        for (int i = 1; i < n + 2; i++) {
            for (int j = 0; j < i; j++) {
                if (fuels[j][0] > fuels[i][0] || fuels[j][1] > fuels[i][1]) {
                    continue;
                }

                if (dp[j] < dist(j, i)) {
                    continue;
                }

                dp[i] = Math.max(dp[i], dp[j] - dist(j, i) + fuels[i][2]);
            }
        }

        return dp[n + 1] >= 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(br.readLine());

        fuels = new int[n + 2][3];

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            fuels[i][0] = Integer.parseInt(st.nextToken());
            fuels[i][1] = Integer.parseInt(st.nextToken());
            fuels[i][2] = Integer.parseInt(st.nextToken());
        }
        fuels[0] = new int[]{1, 1, 0};
        fuels[n + 1] = new int[]{r, c, 0};

        Arrays.sort(fuels, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return (o1[0] + o1[1]) - (o2[0] + o2[1]);
            }
        });

        int s = 1, e = r + c - 2;

        while (s <= e) {
            int mid = (s + e) / 2;

            if (find(mid)) {
                e = mid - 1;
            } else
                s = mid + 1;
        }

        System.out.println(s);
    }
}

너무 당연하게 dfs로 생각했지만 dp와 이분탐색을 섞어서 푸는 색다른 문제였다.

함께 읽으면 좋은 글

코딩 테스트2026-04-02

5430번 - AC

함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…

코딩 테스트2026-04-02

1966번 - 프린터 큐

여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…

코딩 테스트2026-03-29

1158 - 요세푸스 문제

1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.

코딩 테스트2026-03-29

2164번 - 카드2

1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.

← 서재 목록으로 돌아가기