알고리즘/알문풀(백준, 프로그래머스, 코드트리)

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

ragabys 2023. 10. 12. 14:53

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

 

18186번: 라면 사기 (Large)

라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i

www.acmicpc.net

이전에 풀었던 boj 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);
    }
}

 

실행 시간은 다음과 같다.

저작자표시 비영리 변경금지