오늘 풀어볼 문제는 ⭐라면 사기(small)이란 문제다.

1. 문제 요약

• i번째 공장에서 Ai개 만큼 라면 정확하게 구매해야 함
• 라면 구매법은 3가지
  • i번째 공장 / 라면 1개 / 3원
  • i, i+1번째 공장 / 라면 2개 / 5원
  • i, i+2번째 공장 / 라면 3개 / 7원
• 최소 구매 금액 구하기

1.1 입력

• 라면 공장, 라면개수 최대 10만
• 시간 0.5초

---

2. 접근 알고리즘

처음 생각한 알고리즘은 다음과 같다.
일단 각 공장에서 구매해야 하는 라면의 개수를 담은 배열을 factory라 칭했다.

여러개의 반례를 들어본 결과 다음과 같은 규칙을 생각해냈다.

• 라면을 사다 i+1, i+2의 공장에서 라면의 개수가 0이 되는 일이 발생해서는 안된다.
• factory[i+1] > factory[i+2] 라면, 3개의 라면을 살 수 있더라도 2개의 라면부터 구매해야 한다.

여기서 2번째 조건이 정말 중요한데, 해당 규칙을 찾아놓고 좀 많이 헤맸다. 더 구체적인 규칙을 세우면서 코드가 좀 많이 어지러워 졌었다.

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

public class Main {
    static int N;
    static long answer=0;
    static int [] factory;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        factory = new int[N+2];
        st = new StringTokenizer(br.readLine());

        for(int i=0; i<N; i++) {
            factory[i]= Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<N; i++) {
            if(factory[i]==0) continue;
            if(factory[i]==factory[i+2] && factory[i] < factory[i+1]) buyTwo(i);
            else if(factory[i+1]-factory[i]==factory[i+2] && factory[i+2]==factory[i+3]) buyTwo(i);
            else if(factory[i+1]>factory[i+2]&&factory[i+1]-factory[i+2] >=2) buyTwo(i);
            else buyThree(i);
        }

        System.out.println(answer);
    }

    static void buyThree (int i) {
        if(factory[i+1]!=0 && factory[i+2]!=0) { //라면 3개 살 수 있을때
            int minus = Math.min(factory[i+1], factory[i+2]);
            minus = Math.min(factory[i], minus);

            factory[i] -= minus;
            factory[i+1] -= minus;
            factory[i+2] -= minus;

            answer += (minus* 7L);
        }
        buyTwo(i);
    }

    static void buyTwo (int i) {
        if(factory[i+1]!=0 && factory[i]!=0) { //라면 2개 살 수 있을 때
            int minus = Math.min(factory[i+1], factory[i]);

            factory[i] -= minus;
            factory[i+1] -= minus;

            answer += (minus* 5L);
        }
        if(factory[i]!=0) { //라면 1개 살 수 있을 때
            answer += (factory[i]* 3L);
            factory[i]=0;
        }
    }
}

이런 식으로 정답 시도를 했지만 틀렸당^^;

2. 정답 알고리즘

라면 구매 금액을 보면, 당연히 많이 살 수록 더 싸다.
그러나 2 4 2 이라는 순서대로 주어졌을때 무조건 순서대로 3개 -> 2개 -> 1개 순으로 된다면?

2 4 2 2 -> 0 2 0 2 (+14원) -> 0 0 0 2 (+6원) -> 0 0 0 0 (+6원) : 총 26원!

그러나 정답은 다음과 같다!

2 4 2 2 -> 0 2 2 2 (+10원) -> 0 0 0 0 (+14원) : 총 24원!

이유는 아까 찾았던 라면을 사다 i+1, i+2의 공장에서 라면의 개수가 0이 되는 일이 발생해서는 안된다. 라는 규칙 때문이다.

이런 일은 i+1에서 사야할 라면 개수 > i+2 에서 사야할 라면 개수 일때만 발생한다.

그렇다면! 위와 같은 상황일때 i+1과 i+2의 라면차를 최대한 줄여주면 된다. 그 방법이 바로 라면을 2개씩 먼저 사서 i+1의 라면을 소비하는 것이다.

3. 코드

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

public class Main {
    static int N;
    static int answer=0;
    static int [] factory;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        factory = new int[N+2];
        st = new StringTokenizer(br.readLine());

        for(int i=0; i<N; i++) {
            factory[i]= Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < N; i++) {
            if (factory[i + 1] > factory[i + 2]) {
                buyTwo(factory[i], factory[i+1]-factory[i+2], i);  // 예외적으로 먼저 두 공장 처리
            }
            buyThree(i);    // 가장 우선적으로 싸게 처리
            buyTwo(factory[i], factory[i+1], i);      // 남은 두 공장 처리
            buyOne(i);      // 마지막 단독 처리
        }

        System.out.println(answer);
    }

    static void buyThree(int i) {
        int minus = Math.min(factory[i+1], factory[i+2]);
        minus = Math.min(factory[i], minus);

        factory[i] -= minus;
        factory[i+1] -= minus;
        factory[i+2] -= minus;

        answer += (minus* 7);
    }

    static void buyTwo (int value1, int value2, int i) {
        int minus = Math.min(value1, value2);
        factory[i] -= minus;
        factory[i+1] -= minus;
        answer += (minus* 5);
    }

    static void buyOne(int i) {
        answer += (factory[i]* 3);
        factory[i]=0;
    }
}