[백준] 13305 - 주유소 (자바)

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 IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int node_num = Integer.parseInt(br.readLine());
        long[] distance = new long[node_num-1];
        long[] price = new long[node_num];


        //거리 입력
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<node_num-1; i++) {
            distance[i] = Long.parseLong(st.nextToken());
        }

        //리터 당 기름값 입력
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<node_num; i++) {
            price[i] = Long.parseLong(st.nextToken());
        }
        long sum = 0;

        //distance에 해당하는 price 처리하여 result에 담기.
        for (int i = 0; i < node_num-1; i++) {
            long small = price[i];
            for (int j = 0; j <= i; j++) {
                if (price[j] < small) {
                    small = price[j];
                }
            }
            sum  += small * distance[i];
        }
        System.out.println(sum);
    }
}

- for를 두 개 쓰니 시간이 어마어마하게 많이 걸렸다. (4s)

 

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 IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int node_num = Integer.parseInt(br.readLine());
        long[] distance = new long[node_num-1];
        long[] price = new long[node_num];


        //거리 입력
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<node_num-1; i++) {
            distance[i] = Long.parseLong(st.nextToken());
        }

        //리터 당 기름값 입력
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<node_num; i++) {
            price[i] = Long.parseLong(st.nextToken());
        }
        long sum = 0;
        long min_price = price[0];

        //distance에 해당하는 price 처리하여 sum에 더하.
        for (int i = 0; i < node_num-1; i++) {

            if(min_price > price[i]) {
                min_price = price[i];
            }
            sum  +=  min_price * distance[i];
        }
        System.out.println(sum);
    }
}

- for문을 하나 없애는 방식으로, 시간을 1/10으로 줄였다.

- 굳이 사용 가능한 price[]를 모두 탐색할 필요는 없다.

- 조건문을 통해, min_price를 갱신하는 방법을 사용하자.