[백준] 13305번 주유소 - 그리디(Greedy, 탐욕법) JAVA

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

13305번: 주유소

코드설명

그리디(Greedy, 탐욕법)을 활용합니다.

 

여러가지 생각이 났습니다.

처음에는, 최적 부분구조를 성립시키는가? 라는 방향으로 문제를 접근했습니다.

func(int 현재도시위치, int 현재기름통의 기름양) : 현재 도시 위치에서 현재 기름통의 기름양을 가지고 있을떄, 최소의 양을 통해서 마지막 위치까지 도달한다.

라는 함수를 세워서 메모이제이션을 적용해서 진행할 수도 있습니다. 

하지만, 해당 방안 또한 메모이제이션을 적용했지만, 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수입니다.

그리고 N은 100,000 이므로, 10^9 * 10^5 의 공간복잡도가 필요하게 되며, 메모이제이션으로 중복연산은 피할 수 있지만, 최악의 경우 10억개의 연산은 반드시 발생합니다. (최악의 경우 10초 발생)

 

그대신에, 그리디 방식을 사용합니다.

가장 주유소의 가격 작은 도시에서 남은 거리만큼 모두 주유하는 것이 효율적임은 직관적으로 알 수 있습니다.

이떄, 제가 맞닥뜨린 문제는, 

첫번쨰 위치에서 (두번쨰부터 ~마지막까지 도시 중 본인보다 작은 금액의 도시가 있으면 그 도시 전까지만 구매)

이런식으로 생각했습니다.

하지만, 이렇게 할경우 여전히 최악의 경우 50억((N이 도시의 개수일때,  (N)(N+1)/2)의 연산이 발생합니다. 

 

그 대신에, 가장 주유금액이 낮은 도시의 금액을 가지면서, 다음 도시까지의 거리만큼 주유를 하면 됩니다. 그렇게 되면 단 N번의 연산으로 해결이 가능합니다. 

 

아래는 각 도시간의 기름값의 가격입니다.
5 2 4 1 여기서
5 2 2 1 로 계산하는 방법입니다.
위의 방법으로 할시
3번째 도시에서 원래 기름값인 4로 계산하는 것이 아닌, 2번째 도시에서 미리 계산하는것과 같습니다.
마지막 도시는 이동하지 않으므로 무시합니다.

코드

정답코드입니다.

package Main;

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

public class Main {
    private static int N, T, K, M;
    private static int[] arr;
    private static int[] dist;
    private static long answer = 0;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		dist = new int[N-1];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N-1;i++) {
			dist[i] = Integer.parseInt(st.nextToken());
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		long smallestPrice = 1000000001;
		for(int i=0;i<N-1;i++) {
			if(smallestPrice > arr[i]) {
				smallestPrice = arr[i];
			}
			answer += smallestPrice * dist[i];
		}
		System.out.println(answer);
    }
    
    
}

 

public class Main {

	public static int N;
	public static long[] distance, oilCost;
	public static long sum=0,minCost=0;
	public static void main(String[] args) {		
		Scanner sc = new Scanner(System.in);
		
		N=sc.nextInt();
		distance = new long[N-1];
		oilCost = new long[N];
		for(int i=0;i<N-1;i++) {
			distance[i] = sc.nextLong();
		}
		for(int i=0;i<N;i++) {
			oilCost[i] = sc.nextLong();
		}
		sum=0;
		minCost = oilCost[0];
		for(int i=0;i<N-1;i++) {
			if(oilCost[i] < minCost) {
				minCost = oilCost[i];
			}
			sum+=(minCost * distance[i]);
		}
		System.out.println(sum);
	}
	
}