13305번 주유소

문제링크 : www.acmicpc.net/problem/13305

13305번: 주유소

---

---

 

<알고리즘>

  1) 요금이 저렴한 정류소에서 더 저렴한 정류소가 나올때까지의 거리 합산

  2) 요금이 저렴한 정류소의 요금 * 거리를 더해가면서 합산

 

 

 

버전 1. 최소 요금 정류소 도착시 뒤 거리 전부 계산 가능/ 그 전까지는 저렴한 요금소에서 다음 정류소 보면서 충전

          ( 메모리 : 41340KB   시간 : 364ms )

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

public class Main {
	public static void main(String[] args) {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String s ="";
		try {s=bf.readLine();}catch(IOException e) {}
		int N = Integer.parseInt(s);
		
		//다음 station까지의 거리 
		long distance[] = new long[N-1];
		try {s=bf.readLine();}catch(IOException e) {}
		StringTokenizer st = new StringTokenizer(s);
		for(int i =0;i<N-1;i++) {distance[i] = Integer.parseInt(st.nextToken());}
		
		//station별 요금
		long cost[] = new long[N];
		try {s=bf.readLine();}catch(IOException e) {}
		StringTokenizer st2 = new StringTokenizer(s);
		for(int i =0;i<N;i++) {cost[i] = Integer.parseInt(st2.nextToken());}
		
		//가장 저렴한 station의 요금
		long minimum = cost[0];
		for(int i =0;i<N;i++) {if(minimum>=cost[i]) {minimum = cost[i];}}
		
		long result = 0;
		int index = 0;
		while(index!=N-1) {
			//가장 저렴한 station에 도착하면 이후 거리 분의 요금을 여기서 충전
			if(cost[index]==minimum) {
				long now =0;
				for(int i = index;i<N-1;i++) {now+=distance[i];}
				result+=(now*cost[index]);
				break;
			}
			else {
				long now = distance[index];
				int jump = 0;
				for(int i =1;i<N-index;i++) {
					//다음 station이 지금 스테이션 보다 큰 동안만 jump
					if(cost[index+i]<cost[index]) {
						jump += i;
						break;
					}
					else {now +=distance[index+i];}
				}
				result+=(now*cost[index]);
				index+=jump;
			} 
		}
		System.out.println(result);
	}
}

 

 

버전 2. 요금소 가격을 입력받을때 지금까지 중의 최소 값을 이용해 곱,합산

          ( 메모리 : 41400KB   시간 : 364ms )

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

public class Main {
	public static void main(String[] args) {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String s ="";
		try {s=bf.readLine();}catch(IOException e) {}
		int N = Integer.parseInt(s);
		
		//다음 station까지의 거리 
		long distance[] = new long[N];
		try {s=bf.readLine();}catch(IOException e) {}
		StringTokenizer st = new StringTokenizer(s);
		for(int i =0;i<N-1;i++) {distance[i] = Integer.parseInt(st.nextToken());}
		distance[N-1] = 0;
		
		//station별 요금
		long cost[] = new long[N];
		try {s=bf.readLine();}catch(IOException e) {}
		StringTokenizer st2 = new StringTokenizer(s);
		for(int i =0;i<N;i++) {cost[i] = Integer.parseInt(st2.nextToken());}
		
		//가장 저렴한 station의 요금
		long minimum = cost[0];
		long result = 0;
		for(int i =0;i<N-1;i++) {
			if(minimum>=cost[i]) {
				minimum = cost[i];
			}
			result+=(minimum*distance[i]);
		}
		System.out.println(result);
	}
}