[정올][다이나믹] 1491 자동차경주대회

도착시간 기준으로 방문했을때의 최소값을 기록하여 확인 가능하다.

	import java.util.Collections;
	import java.util.LinkedList;
	import java.util.Scanner;
	/**
	* 정올, 1491
	* 자동차경주대회
	*
	* @author whitebeard-k
	*
	*/
	public class Problem1491 {
	static int CAR_DIST;
	static int N;
	static int[] dist;
	static int[] time;
	static int[] dpTime;
	static int[] dpStation;
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	CAR_DIST = sc.nextInt();
	N = sc.nextInt();
	int distSum = 0;
	dist = new int[N + 2];
	for (int i = 1; i <= N + 1; i++) {
	dist[i] = sc.nextInt();
	distSum += dist[i];
	}
	time = new int[N + 2];
	for (int i = 1; i <= N; i++)
	time[i] = sc.nextInt();
	dpTime = new int[N + 2];
	dpStation = new int[N + 2];
	sc.close();
	if (CAR_DIST >= distSum) {
	System.out.println(0);
	return;
	}
	for (int i = 1; i < dist.length; i++) {
	int currentDist = CAR_DIST - dist[i];
	int currentTime = time[i];
	int min = Integer.MAX_VALUE;
	for (int j = i - 1; j >= 0; j--) {
	if (currentDist < 0)
	break;
	if (currentDist >= 0 && min >= dpTime[j] + currentTime) {
	min = dpTime[j] + currentTime;
	dpStation[i] = j;
	}
	currentDist -= dist[j];
	}
	dpTime[i] = min;
	}
	// System.out.println("dist -------------");
	//
	// for (int n : dist)
	// System.out.printf("%3d ", n);
	//
	// System.out.println("\ntime -------------");
	//
	// for (int n : time)
	// System.out.printf("%3d ", n);
	//
	// System.out.println("\ndpTime -------------");
	//
	// for (int n : dpTime)
	// System.out.printf("%3d ", n);
	//
	// System.out.println("\ndpStation -------------");
	//
	// for (int n : dpStation)
	// System.out.printf("%3d ", n);
	System.out.println(dpTime[N + 1]);
	LinkedList<Integer> list = new LinkedList<>();
	int index = N + 1;
	while (true) {
	int station = dpStation[index];
	if (station == 0)
	break;
	list.add(station);
	index = station;
	}
	System.out.println(list.size());
	Collections.reverse(list);
	for (int n : list)
	System.out.printf("%d ", n);
	}
	}

view raw Problem1491.java hosted with ❤ by GitHub

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=763&sca=3050