[알고리즘] BOJ 18186 라면 사기(Large) (JAVA)

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

18186번: 라면 사기 (Large)

이전에 풀었던 boj 18185 라면 사기(Small) 문제의 확장된 버전이다.

https://ragabys.tistory.com/14

BOJ 18185 라면 사기(Small) (JAVA)

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

18185번: 라면 사기 (Small)

기존의 문제에서 공장의 개수 N과 공장에서 사야하는 라면의 최대 갯수가 10^4에서 10^6으로 증가했다.

또한 기존의 3,5,7원으로 정해진 가격에서 B, B+C, B+2C 라는 형태로 테스트 케이스마다 입력받은 값에 따라

가격이 바뀌게 정해졌고, B와 C의 최대값도 10^6으로 정해져있다.

기존의 문제에서 int형으로 선언한 변수 중 일부 변수를 long으로 선언했다.

또한 기존 문제에서 접근하는 방식은 그대로 가져왔고(이전 글 참조), 기존의 문제에서 3원, 5원, 7원으로 정해져있는 것과

달리 B와 C로 입력받은 값에 따라 바뀌기 때문에, 이와 관련된 조건을 추가했다.

만약 B<C인 경우, i번째와 i+1번째 공장에서 하나씩 구매할 때 발생하는 비용 B+C가

i번째와 i+1번째 공장에서 각각 구매할 때 발생하는 비용 B+B에 비해 크기 때문에,

비용 B < 비용 C인 경우 C의 값을 B로 바꿔주면 된다.

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class boj18186 {

    static int N;

    static long B, C, cost;

    static int ramen[];

    public static void greedy() {

        int i, tmp;

        if (B < C) {

            C = B;

        }

        for (i = 1; i <= N; i++) {

            if (ramen[i + 1] > ramen[i + 2]) {

                // 두번째 라면이 세번째보다 많은 경우

                // 7원 구매를 최대한 하기 위해 최소한으로 5원 구매를 함

                tmp = Math.min(ramen[i], ramen[i + 1] - ramen[i + 2]);

                cost += ((B + C) * tmp);

                ramen[i] -= tmp;

                ramen[i + 1] -= tmp;

                tmp = Math.min(ramen[i], Math.min(ramen[i + 1], ramen[i + 2]));

                cost += ((B + 2 * C) * tmp);

                ramen[i] -= tmp;

                ramen[i + 1] -= tmp;

                ramen[i + 2] -= tmp;

            } else {

                // 두번째 라면이 세번째보다 적은 경우

                // 7원 구매를 최대한 한 후 5원 구매를 함

                tmp = Math.min(ramen[i], ramen[i + 1]);

                cost += ((B + 2 * C) * tmp);

                ramen[i] -= tmp;

                ramen[i + 1] -= tmp;

                ramen[i + 2] -= tmp;

                tmp = Math.min(ramen[i], ramen[i + 1]);

                cost += ((B + C) * tmp);

                ramen[i] -= tmp;

                ramen[i + 1] -= tmp;

            }

            cost += (B * ramen[i]);

        }

    }

    public static void pre() throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        B = Long.parseLong(st.nextToken());

        C = Long.parseLong(st.nextToken());

        ramen = new int[N + 3]; // N번째 라면까지 한번에 계산하기 위해 N+3의 크기로 설정

        cost = 0;

        st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= N; i++) {

            ramen[i] = Integer.parseInt(st.nextToken());

        }

    }

    public static void main(String args[]) throws IOException {

        pre();

        greedy();

        System.out.println(cost);

    }

}

 

실행 시간은 다음과 같다.