알고리즘/BJ

[BJ] 13305 주유소

9_yoon 2022. 2. 19. 00:10
728x90
반응형

문제

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

풀이 방법

이동을 하면서 주유비가 최소인 도시에서, 다음 주유비 최소인 도시를 만나기 전까지의 거리만큼 주유를 다하고 가야겠다고 생각을 했다. 그래서 생각한게
위와 같은 로직이였다. 
어짜피 두 개의 결과 값이 같은 점을 이용해서 나는 min에 현재 최소주유비용을 저장하고 한칸씩 이동을 하면서 min보다 더 작은 주유비용이 나오기 전까지는 해당 거리를 계속 min과 곱하고 sum에 더해주는 식으로 구현했다. 

제출 코드

import java.io.*;
import java.util.*;

public class BJ_13305_주유소 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken())-1; //마지막 도시는 사용하지 않기 때문에 
		long[] dist = new long[N];
		long[] prices = new long[N];
		
		st = new StringTokenizer(br.readLine());
		//거리 정보 저장
		for (int i = 0; i < N; i++) {
			dist[i] = Long.parseLong(st.nextToken());
		}
		
		//기름 정보 저장
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			prices[i] = Long.parseLong(st.nextToken());
		}
		long minOil = Long.MAX_VALUE; 
		long sum =0; 
		for (int i = 0; i < N; i++) {
			//만약 현재 minOil 보다 더 작은 기름값이 나오면 minOil을 교체 
			if(prices[i]< minOil) minOil = prices[i];
			//이전까지 도시들중에서 가장 작았던 기름 값 * 거리를 총합에 더해주기
			sum+= minOil * dist[i];
		}
		
		System.out.println(sum);
	}
}

 

728x90
반응형