자동차경주대회 1491 (백준2651)

문제 링크

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=763&sca=99&sfl=wr_hit&stx=1491 

JUNGOL

https://www.acmicpc.net/problem/2651

2651번: 자동차경주대회

정류장의 수가 100개 이다. 

백덤블링 하면서봐도 완탐으론 안된다. DP인거 같은데..... 일단 그래도 어느정도 통과하는지 확인을 위해 완탐을 시도해 보았다.

 

완전 탐색 코드 

분명히 터지겠지만 일단 트라이

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

public class Main1491 {
	static int k;
	static int n;
	static int min;
	static int cnt;
	static String ans;
	static int[] dist;
	static int[] time;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		k=Integer.parseInt(br.readLine());
		n=Integer.parseInt(br.readLine());
		dist=new int[n+1];
		time=new int[n+1];
		StringTokenizer st=new StringTokenizer(br.readLine());
		for(int i=0;i<=n;i++) {
			dist[i]=Integer.parseInt(st.nextToken());
		}
		st=new StringTokenizer(br.readLine());
		for(int i=1;i<=n;i++) {
			time[i]=Integer.parseInt(st.nextToken());
		}
		min=Integer.MAX_VALUE;
		cnt=0;
		ans="";
		solv(dist[0],0,1,0,"");
		System.out.println(min);
		System.out.println(cnt);
		System.out.println(ans);
	}
	private static void solv(int d, int t,int idx,int count,String now) {
		if(idx==n+1) {
			if(t<min&&d<=k) {
				min=t;
				cnt=count;
				ans=now;
			}
			
			return;
		}
		
		if(d+dist[idx]>k) {
			solv(dist[idx],t+time[idx],idx+1,count+1,now+idx+" ");
			return;
		}
		if(t>=min)return;
		solv(d+dist[idx],t,idx+1,count,now);
		solv(dist[idx],t+time[idx],idx+1,count+1,now+idx+" ");
	}
}

응 어림도 없지^^

사실 시간이 10배 차이나지만 된다고하는데 코드가 잘못됨ㅋㅋㅋㅋㅋ디버깅 실패 ㅎ

 

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 NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int k=Integer.parseInt(br.readLine());
		int n=Integer.parseInt(br.readLine());
		long[] dist=new long[n+2];//dist 법위 2^31-1
		int[] time=new int[n+2];//정류소 개수 100개
		int[] parent=new int[n+2];//이전에 선택된 정류소 번호
		StringTokenizer st=new StringTokenizer(br.readLine());
		for(int i=1;i<=n+1;i++) {
			dist[i]=Long.parseLong(st.nextToken())+dist[i-1];//출발지 0, 도착지 n+1
		}
		st=new StringTokenizer(br.readLine());
		for(int i=1;i<=n;i++) {
			time[i]=Integer.parseInt(st.nextToken());
		}
		//----------입력
		long[] dp=new long[n+2];
		for(int i=1;i<=n+1;i++) {
			dp[i]=Long.MAX_VALUE;
		}
		//----------초기화
		for(int i=1;i<=n+1;i++) {
			for(int j=i-1;j>=0;j--) {
				if(dist[i]-dist[j]>k) {
					break;
				}//k 초과시 중간에 정류소를 들렀어야 했으므로 아웃
				if(dp[i]>dp[j]+time[j]) {//i 까지 가기 위해 j 정류소를 들르는것이 시간이 더 적을 경우 
					dp[i]=dp[j]+time[j];
					parent[i]=j;//i 에 가기 위해서는 j 정류소를 거쳤으므로
				}
			}
		}
		int i=parent[n+1];
		String ans="";
		int cnt=0;
		while(i!=0) {
			ans=i+" "+ans;
			i=parent[i];
			cnt++;
		}//i의 이전 정류소가 출발지 (0) 일때까지 경로 탐색
		System.out.println(dp[n+1]);//총 시간
		if(cnt==0)return;//cnt가 0일 경우 끝냄(정올에선 있어야 답, 백준에선 없어야 답)
		System.out.println(cnt);// 정류소 개수
		System.out.println(ans);//경로
	}
}

풀이

범위가 Long 인데 int 로 해서 디버깅이 오래 걸렸다.... 범위 주의하자