백준 13305: 주유소

풀이

• 현재 위치한 도시보다 진행할 도시 중 기름값이 싼 도시가 있으면 현재 도시에서 기름값이 싼 도시까지 갈 기름을 채우고, 현재 위치한 도시를 기름값이 싼 도시로 한다.
• 단, 기름값이 싼 도시가 마지막 도시인 경우는 제외한다.(현재 도시에서 마지막 도시까지 갈 기름을 채운다.)

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

public class Problem13305 {

    //맨 처음부터 선택 앞 도시들 중 비용이 작은 도시가 존재(마지막 도시는 제외)하면 현재도시에서 그 도시까지 갈수 있는 최소한만 채운다.
    //도시이름, [도시의 기름값, 다음 도시까지의 거리]
    static int cityNum;
    static int[] roadLen, oilPri;
    static long totalOilPri = 0;

    //현재 도시부터 다음 도시 중 현재 도시보다 비용이 작은 도시가 존재하면(마지막 도시는 제외)하면 현재 도시에서 그 도시까지의 거리를 구하고 기름을 채운다.
    //그리고 이동한 도시의 인덱스를 반환한다
   public static int move(int curCity){
       int nextCity = -1;
       long nextPrice = -1;
       long curPri = oilPri[curCity];
       long totalOil = 0;
       for(int i = curCity+1; i < oilPri.length; i++){
           //현재 도시부터 다음 도시까지 이동하기 위한 기름 누적
           totalOil += roadLen[i-1];
           if(oilPri[i] < curPri){
               nextCity = i;
               nextPrice = oilPri[i];

               //현재 도시에서 주유할 기름
               totalOilPri += totalOil * oilPri[curCity];
               break;
           }
       }
       //다음 도시 중 현재 도시보다 싼 가격이 없는 경우(현재도시가 도착지점까지 가장 싼 값)
       if(nextPrice == -1){
           //현재 도시에서 주유할 기름(마지막 도시까지 주유)
           totalOilPri += totalOil * oilPri[curCity];
           return oilPri.length-1;
       }

       return nextCity;
    }




    public static void main(String[] arg) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        cityNum = Integer.parseInt(br.readLine());
        roadLen = new int[cityNum-1];
        oilPri = new int[cityNum];

        String roadStr = br.readLine();
        StringTokenizer roadSt = new StringTokenizer(roadStr, " ");
        for(int i = 0; i < cityNum-1; i++){
            roadLen[i] = Integer.parseInt(roadSt.nextToken());
        }

        String oilStr = br.readLine();
        StringTokenizer oilSt = new StringTokenizer(oilStr, " ");
        for(int i = 0; i < cityNum; i++){
            oilPri[i] = Integer.parseInt(oilSt.nextToken());
        }

        int curCity = 0;
        while(curCity != oilPri.length-1){
            curCity = move(curCity);
        }

        System.out.println(totalOilPri);
        double d = Double.MAX_VALUE;
        long l = Long.MAX_VALUE;
        System.out.println(d);
        System.out.println(l);

    }
}

주의할 점

• 비용의 최댓값은 10^9 *10^9 = 10^18이므로 4바이트 자료형인 int로는 표현할 수 없다.
• 첫 풀이에서는 double 자료형으로 풀었지만 풀리지 않았고(왜 풀리지 않는지 몰라서 한참을 헤맸다.) double자료형이 10^18을 표현가능한지 계산해 보았다.

1. 10^18을 이진수로 변환 : 110111100000101101101011001110100111011001000000000000000000
2. 정규화 : 1.10111100000101101101011001110100111011001000000000000000000 * 2^59
3. 지수부 : 59 + 1023 = 1082 이진수 : 10000111010(11Bit)
4. 가수부 : 10111100000101101101011001110100111011001000000000000000000(59Bit)
5. double 자료형의 지수부는 11Bit, 가수부는 52Bit (+ 부호비트 1Bit까지 포함하면 64Bit ->8바이트형 자료형) 까지이므로 표현 불가능하다.

   부동소숫점 변환 참조
   https://greatzzo.tistory.com/56

• double 자료형과 같이 8바이트 자료형이면서 정수만 표현가능한 long을 사용하자.