BOJ) 자동차경주대회

자동차경주대회

2651번: 자동차경주대회

풀이

 

이 문제는 DP를 활용해서 풀었다.

정비소의 위치와 걸리는 시간을 담을 배열을 각각 선언해서 값을 저장해줬다.

이 때, 출발 지점인 0과 도착 지점인 마지막 위치도 같은 배열에 저장해서 도로의 출발점과 도착점까지 탐색하도록 설정했다.

 

각 정비소를 들르면서, 이전까지 최대 이동거리인 maxDist안에 있는 정비소를 찾아 걸리는 시간의 최소값을 구했다.

해당 정비소가 최소 시간을 만족하기 때문에, 걸리는 시간을 더해주면서 마지막 도착지점까지 시간이 저장되게 설정했다.

 

또한, 각 정비소에서 최소 시간을 찾은 인덱스를 저장해서, 들르는 정비소를 저장해주었다. (Parents 개념)

걸리는 시간은 TimeArr의 마지막 인덱스 (도착 지점)을 통해 출력해줬다.

들른 정비소 수와 번호는 ArrayList를 생성해서, 도착지점부터 시작해서 이전에 저장한 parents 정비소들을 출력해주었다.

 

로직

 

1. 최대 이동거리 maxDist, 정비소 지점마다 이동거리 배열(repairSpots), 해당 정비소에서 걸리는 정비 시간을 저장하는 배열(timeArr) 변수를 선언 및 입력 값으로 초기화 해준다.

2. repairSpots는 출발 지점과 도착 지점도 저장하기 위해, 입력받은 크기 +2 크기 만큼 할당한다.

3. 각 정비소를 돌면서, 해당 정비소를 들르기 이전에 maxDist 안에있는 정비소 중에 최소 정비 시간인 정비소를 찾는다.

 3-1. 시작점 0~maxDist 까지는 시작점에 정비소가 있다고 가정하고, timeArr를 0으로 나뒀기 때문에 최소값이 0으로 된다.

 3-2. 해당 정비소에 찾은 정비소의 번호를 spotArr(Parents 개념)에 저장해준다.

 3-3. 해당 정비소에 찾은 최소 정비 시간을 더해준다. (최소 정비시간을 누적 시켜 답을 구하기 위해서)

4. timeArr의 마지막 인덱스(도착지점)에는 최소 시간이 저장되어있으므로, 출력해준다.

5. ArrayList를 생성해서, 들른 정비소를 저장해준다.

6. spotArr의 마지막 인덱스(도착지점)에 저장된 정비소 번호부터 저장하면서, 들른 정비소를 계속해서 추가해준다.

7. ArrayList의 크기 = 들른 정비소의 갯수 , 따라서 정비소의 갯수인 크기를 출력해준다.

8. ArrayList의 마지막 인덱스부터 0번째 인덱스까지 출력해준다. (들른 정비소 오름차순)

 

코드

 

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

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

        int maxDist = Integer.parseInt(br.readLine());
        int repairs = Integer.parseInt(br.readLine())+2;  // 출발점과, 도착점 저장하기 위해 +2
        int[] repairSpots = new int[repairs];
        int[] timeArr = new int[repairs];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<repairs; i++) {
            repairSpots[i] = Integer.parseInt(st.nextToken()) + repairSpots[i-1];
        }

        st = new StringTokenizer(br.readLine());
        for(int i=1; i<repairs-1; i++) {
            timeArr[i] = Integer.parseInt(st.nextToken());
        }
        br.close();

        solution(maxDist,repairs,repairSpots,timeArr);
    }

    private static void solution(int maxDist, int repairs, int[] repairSpots, int[] timeArr) {
        int[] spotArr = new int[repairs];
        for(int i=1; i<repairs; i++) {
            int min = Integer.MAX_VALUE;
            for(int j=i-1; j>=0; j--) {
                if(repairSpots[i] - repairSpots[j] > maxDist) {
                    break;
                }
                if(min > timeArr[j]) {
                    min = timeArr[j];
                    spotArr[i] =j;
                }
            }
            if(min != Integer.MAX_VALUE) {
                timeArr[i] += min;
            }
        }
        System.out.println(timeArr[repairs-1]); // 걸린 시간

        int prev = spotArr[repairs-1];
        ArrayList<Integer> spotList = new ArrayList<>();

        while(prev !=0) {
            spotList.add(prev);
            prev = spotArr[prev];
        }
        System.out.println(spotList.size());
        for(int i = spotList.size()-1; i>=0; i--) {
            System.out.print(spotList.get(i) + " ");
        }
    }
}
// https://www.acmicpc.net/problem/2651