[알고리즘] BOJ 18185 라면 사기(Small) (JAVA)

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

18185번: 라면 사기 (Small)

어쩌다 알게 된 문제인데 어쩌다 보니 백준에서 처음으로 플레 이상 푼 문제가 되었다.

문제 푸는 방식 고민을 실제 시간으로는 (며칠간 걸쳐서 총 합)몇 시간정도 한 것 같은데,

풀고 나서 든 생각은 골드5 문제인 N-Queen 마냥  고려하지 못하는 부분 때문에

solved 티어가 좀 높게 잡힌 문제가 아닌가라는 생각이 들었다.

처음 문제를 접근할때는 무조건 최대한 7원 구매(i, i+1, i+2)를 한 뒤,

그 다음 남은 수만큼 구매를 하는 방식으로 접근하면 되지 않나?라고 생각했지만,

실제로는 7원 구매를 하고 난 뒤 남은 라면을 구매하기 위해 오히려 3원 구매 횟수가 많아지는 경우가 생겼다.

그래서 i+1번째 라면의 수량에 따라 조건을 나눠 접근했다.

 

만약 i+1번째 라면의 갯수가 i+2번째 라면의 갯수보다 많은 경우,

i번째와 i+1번째 라면을 최소한 5원 구매를 하고, 7원 구매를 최대한 하는 식으로 구해줘야 한다.

 

i+1번째 라면이 i+2번째 라면보다 적은 경우에는 처음 생각했던 방식대로

최대한 7원 구매를 해준 뒤 5원 구매로 i번째와 i+1번째 라면을 최대한 구매하고 나머지를 구매하는 식으로 구하면 된다. 

 

이렇게 알고리즘을 구성한 이유로는, 무조건 7원 구매를 하는 경우 혹은 5원 구매를 몇 번 해야하는 가에 있어서 몇가지 반례가 생기기 때문이다.

 

우선, 7원 구매를 우선적으로 한다는 방법의 반례로는 2 4 2 2 의 경우,

7원 구매 2번 => 0 2 0 2 => 3원 구매 총 4번 => 0 0 0 0 => 총 합계 26원이 필요하지만,

5원 구매 2번 => 0 2 2 2 => 7원 구매 2번 => 0 0 0 0 => 총 합계 24원이 필요한 경우가 생긴다.

이러한 경우로 인해 5원 구매 또한 적절히 해야한다는 생각이 들었는데, 위 경우에서 뒤에 진행될 계산 과정에서

5원이상 구매를 최대한 해주기 위해선 i+1번째 값과 i+2번째 값을 맞춰야한다는 생각이 들었다.

값을 맞추는 과정에서 i+1 값이 i+2 값보다 작은 경우에는 최대한 7원 구매를 해준뒤 다음 값인 i+1로 넘어가면 되고,

i+1값이 i+2 값보다 큰 경우i+1값을 i+2값과 맞춘후, 다음 과정에서 5원 구매를 해주기 위해 i와 (i+1) - (i+2)를 비교한 만큼

i번째와 i+1번째 라면을 5원 구매를 했다.

import java.io.*;

import java.util.*;

public class boj18185 {

    static int N,cost;

    static int ramen[];

    public static void greedy() {

        int i,tmp;

        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 += (5 * tmp);

                ramen[i] -= tmp;

                ramen[i + 1] -= tmp;

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

                cost += (7 * tmp);

                ramen[i] -= tmp;

                ramen[i + 1] -= tmp;

                ramen[i + 2] -= tmp;

            } else {

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

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

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

                cost += (7 * tmp);

                ramen[i] -= tmp;

                ramen[i + 1] -= tmp;

                ramen[i + 2] -= tmp;

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

                cost += (5 * tmp);

                ramen[i] -= tmp;

                ramen[i + 1] -= tmp;

            }

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

        }

    }

    public static void pre() throws IOException {

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

        N = Integer.parseInt(br.readLine());

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

        cost = 0;

        StringTokenizer 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);

    }

}

 

실행시간은 다음과 같다

첫 다이아 문제 Solvedㅎ

다음 문제는 아마도 같은 문제 다른 버전인 라면 사기(Large)를 풀어보게 될 것 같다