[백준] 13305번 - 주유소 (Java) : 100점 & 58점 코드

문제

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

13305번: 주유소

 

풀이

<문제에서 알 수 있는 사실들>

• N : 도시의 개수
• N-1 : 인접한 두 도시를 연결하는 도로의 개수. 
• 처음 도시에서는 기름이 없는 채로 시작한다.
• 각 도시의 주유소에서 1L당 가격으로 기름을 충전할 수 있다.
• 도로를 이동할 때 1km마다 1L의 기름을 사용한다.

<문제 보기로 주어진 문제에서 해를 찾는 과정.>

<새롭게 도출해낸 사실들>

1. 주유 비용을 최소화하기 위해 리터당 가격이 싼 기름을 넣어야 한다.

2. 그러나 그 도시의 주유소는 해당 도시에 도착해야 이용할 수 있다.
2번째 도시의 기름값이 1번째 도시보다 싸다는 것을 알고 있지만, 1번째 도시에서는 2번째 도시의 주유소를 이용할 수 없다. 즉, 선택지가 없으므로 강제적으로 1L에 5원을 주고 기름을 충전해야 한다.ㅍ 

3. 무엇보다도, 처음 도시에서는 무조건 다음 도시까지 가기 위한 기름을 충전해야 한다.
*만약 전체 도시 중 첫 도시의 기름값이 가장 싸다면, 다음 도시까지 가는데 필요한 기름 값 뿐 아니라 첫 도시의 주유소에서 처음~마지막 도시까지 가는 데 필요한 기름을 전부사야 한다.

4. 마지막 도시에서는 더 이상 나아갈 도로가 없으므로, 마지막 도시의 기름 값은 프로그램에서 사용되지 않는다. 입력으로 주어져서 받기는 하나, 사용하지는 않을 예정.

5. 2에서 언급한 바와 같이, 다음 도시의 주유소를 미리 이용할 수 없기 때문에 그때 그때 그나마 지금 나온 것들 중 가장 가격이 싼 기름을 넣어야 한다.(이전까지 나온 도시들의 기름 값 vs 현재 도시의 기름 값)

→ 현재 상황에서 최선의 수를 선택하는 문제이기 때문에 그리디 알고리즘이 적합하다.

 

코드

1차 코드(58점 / 부분성공)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();           // 도시 개수
        int[] road = new int[n - 1];    // 각 도시를 연결하는 도로의 길이 (1km 이동 = 1L 기름 사용)
        int[] oil = new int[n];         // 각 도시에 있는 주유소의 기름 가격 (1L 당 가격)

        for (int i = 0; i < road.length; i++) {
            road[i] = sc.nextInt();
        }

        for (int i = 0; i < oil.length; i++) {
            oil[i] = sc.nextInt();
        }

        // 처음 주유소는 무조건 이용
        int result = oil[0] * road[0];
        int minPrize = oil[0];

        // 마지막 - 1 번째 주유소까지만 이용 가능
        for (int i = 1; i < oil.length - 1; i++) {
            // 지금까지 거친 주유소 중 최저가 vs 현재 주유소
            if (oil[i] < minPrize) {
                result += oil[i] * road[i];
                minPrize = oil[i];
            } else {
                result += minPrize * road[i];
            }
        }

        System.out.println(result);
    }
}

 

2차 코드(100점 / 성공)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());    // 도시 개수

        BigInteger[] road = new BigInteger[n - 1];              // 각 도시를 연결하는 도로의 길이 (1km 이동 = 1L 기름 사용)
        BigInteger[] oil = new BigInteger[n];                   // 각 도시에 있는 주유소의 기름 가격 (1L 당 가격)

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n - 1; i++) {
            road[i] = new BigInteger(st.nextToken());
        }

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            oil[i] = new BigInteger(st.nextToken());
        }

        // 처음 주유소는 무조건 이용
        BigInteger result = oil[0].multiply(road[0]);
        BigInteger minPrize = oil[0];

        // 마지막 - 1 번째 주유소까지만 이용 가능
        for (int i = 1; i < oil.length - 1; i++) {
            // 지금까지 거친 주유소 중 최저가 vs 현재 주유소
            if (oil[i].compareTo(minPrize) < 0) {
                result = result.add(oil[i].multiply(road[i]));
                minPrize = oil[i];
            } else {
                result = result.add(minPrize.multiply(road[i]));
            }
        }

        System.out.println(result);
    }
}

• 기름 값(oil) * 거리(road) 곱셈 과정에서 오버플로우 주의
• 큰 수를 고려해서 각 도시의 기름 값, 거리 길이 등 값을 BigInteger 타입으로 처리한다.

 

java.math.BigInteger 클래스

public class BigInteger extends Number implements Comparable<BitInteger> {
    final int signum;	// 부호. 1(양수), 0, -1(음수)
    final int[] mag;	// 값(magnitude)
}

• 가장 큰 정수형 타입인 long으로 표현할 수 있는 값(10진수로 19자리 정도) 보다 큰 값을 다뤄야 할 때 사용한다.
• 내부적으로 int배열을 사용해서 값을 다룬다.
• 자릿수가 큰 정수의 각 자릿 값을 하나씩 배열 요소로 가지고 있는 구조.

 

BigInteger 객체 생성

BigInteger val;
val = new BigInteger("12345678901234567890");	// 문자열로 생성
val = new BigInteger("FFFF", 16);				// n진수(radix)의 문자열로 생성
val = BigInteger.valueOf(1234567890L);			// 숫자로 생성

BigInteger[] array = new BigInteger[10];		// 배열 생성

 

BigInteger 연산

BigInteger은 int, long, float과 같은 기본 자료형이 아니기 때문에 +, -, /, % 과 같은 산술 연산자를 적용할 수 없다. 그대신 BigInteger 타입 자체에서 add(), substract(), multiply() 와 같은 산술연산 기능을 수행하는 함수를 제공한다. 해당 함수들의 반환 값으로 연산 결과를 리턴한다. 이를 BigInteger 타입 변수로 받아서 사용하면 된다.

BigInteger add(BigInteger val)         // 덧셈
BigInteger substract(BigInteger val)   // 뺄셈
BigInteger multiply(BigInteger val)    // 곱셈
BigInteger divide(BigInteger val)      // 나눗셈
BigInteger remainder(BigInteger val)   // 나머지

int        bitCount()      // 2진수로 표현했을 때, 1의 개수(음수는 0의 개수)를 반환
int        bitLength()     // 2진수로 표현했을 때, 값을 표현하는데 필요한 bit수
boolean    testBit(int n)  // 우측에서 n+1번째 비트가 1이면 true, 0이면 false
BigInteger setBit(int n)   // 우측에서 n+1번째 비트를 1로 변경
BigInteger clearBit(int n) // 우측에서 n+1번째 비트를 0으로 변경
BigInteger flipBit(int n)  // 우측에서 n+1번째 비트를 전환 (1이면 0, 0이면 1)

 

BigInteger 비교

BigInteger 연산에서와 같은 이유로 BigInteger 변수에는 >, <, <=, >= 과 같은 등호연산을 적용할 수 없다. BigInteger은 객체로 취급되기 때문에 같은 타입의 BigInteger 변수와 대소 비교를 수행하려면 compareTo() 메서드를 사용해야 한다.

BigInteger val1 = new BigInteger("10");
BigInteger val2 = new BigInteger("20");
if(val1.compareTo(val2) < 0){
	System.out.println("val1은 val2보다 작다.");	// -1
} else if(val1.compareTo(val2) == 0){
	System.out.println("val1은 val2와 같다.");	// 0
} else {
	System.out.println("val1은 val2보다 크다.");	// 1
}