[백준] 18185 라면 사기 (small) java 풀이, 그림으로 이해하기

1. 문제 설명 📌

✨ 문제 링크 ✨

문제 설명이 꽤 직관적이다. 다만 내가 한 번에 이해하지 못한 부분이 있어, 그에 대한 부연 설명을 하고 다음 장으로 넘어가겠다.

교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).

문제의 입력으로 일련의 데이터가 공백으로 구분되어 주어지는데, 해당 데이터의 index = 공장, value = 해당 공장에서 사야할 라면의 개수 라는 뜻이다.

2. 접근 방식 🗃️

KEY WORD: DP

---

(가) 문제에서 주어진 3가지 방법을 숙지한다.

1. i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.
2. i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다.
3. i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 7원이 든다.

(나) 시작점이 되는 i 번째 공장에서는, 무슨 방법을 택하든 3의 비용이 든다. 따라서 i번째 공장의 모든 라면 개수 * 3을 답에 더한다. i번째 공장의 라면은 전부 처리했음으로 arr[i] = 0이 된다.

(다) i + 1 번째 공장의 라면은, 최대 i번째 공장 라면의 개수 만큼 비용 2에 처리할 수 있다. (연속되므로)
따라서 Math.min(i번째 공장 라면의 개수, i+1번째 공장 라면의 개수) 만큼 비용 2에 처리한다.
이후, 잔여 라면을 arr[i+1]에 저장한다.

(라) i+2 번째 공장의 라면은 Math.min(i번째 공장 라면의 개수, i+2번째 공장에서 i+1번째 공장 잔여 라면의 개수를 제외한 라면의 개수) 만큼 비용 2에 처리한다.
이후 잔여 라면을 arr[i+2]에 저장한다.

(마) 1번부터 3번까지를 마지막 공장이 i에 올때까지 반복한다.

---

설명보다 결론이 먼저 나오는 게 이해에 도움이 될 것 같아서 미리 전체 과정을 보여줬다. 아마 (3)번 과정에 대한 설명이 필요할텐데, 지금부터 설명하겠다.

(0) 라면 소비를 바라보는 관점 전환 (횡 ➜ 개별) 💭

많은 사람들이 라면 소비의 관점을 문제에 주어진 조건처럼 횡으로 바라볼 것이다. (예 가로3칸 = 7, 가로 2칸 = 5, 가로 1칸 = 3)

하지만 고맙게도, 3가지 방법 모두, 시작점의 라면 소비 비용은 3이고, 연속된 라면 소비는 비용이 2이다.
따라서 우리는 현재 조회 중인 공장의 라면 하나 하나를 비용 3, i+1, i+2번째 공장의 연속되는 라면의 비용은 2라는 개별적인 관점으로 문제를 접근하겠다.

(1) 이러면 쉬운 문제 아닌가? 🤔

이렇게 시각을 바꾸면 문제가 굉장히 쉬워보인다. 다음 3가지 규칙을 지키면 된다고 생각하기 때문이다.

현재 조회 중인 공장을 i라고 할 때,

• i 번째 공장의 라면들은 3가지 방법 중 뭘 사용해도 비용이 3이므로 총 비용에 i 공장 라면의 개수 * 3을 더한다.
  (전부 사용)
• i+1과 i+2 공장의 라면들은 i번째 공장과 연속된 만큼만 비용이 2이므로, 연속된 모든 것을 전부 비용 2로 총 비용에 더한다.
• i번째 공장의 라면은 전부 소비했음으로, i+1을 현재 조회 중인 공장은 옮기고 다시 처음부터 시작한다. (잔여 라면에 대해서 반복)

하지만 해당 풀이는 다음과 같은 반례가 생긴다.

(2) 반례

위의 예시를 앞에서 설명한 방법대로 풀면 다음과 같이 된다.

최대 3칸부터 확인 하므로 3칸씩 2개 총 비용 14를 먼저 체크하고, 나머지 낱개 2개를 확인해서 총 비용은 20이 된다. 하지만 이것은 최소 비용이 아니다. 최소 비용은 다음과 같다.

0번 공장에서 3번째 방법을 2번 사용해서 비용 14로 계산하지 말고 3번째 방법, 2번째 방법을 번갈아 써서 비용 12를 사용한 다음, 나머지 남은 3개의 라면이 연속됨을 이용해 방법 3으로 비용 7에 계산하는 것이다. 이러면 비용이 총 19가 들어서 최소 비용이 된다.

이와 같이 무작정 방법 3 ➜ 방법 2 ➜ 방법 1의 우선순위로 하는 비용 계산에는 허점이 존재한다. 따라서 *접근방식의 (라) *와 같은 항목이 필요한 것이다.

(3) (라)번에 대한 이해 (반례에 대한 대응)

저러한 반례는 왜 생기는 걸까?

이유는 i+1번째에 잔여 라면이 남아 있다면, i+2,i+3번째와 함께 방법3(연속 3개, 비용 7)이 성립할 가능성이 있기 떄문이다. 따라서 이에 대한 예외처리를 해줘야 한다.

그 결과 *i+2번째에서는 항상 i+1번째의 잔여 라면량 만큼을 미래를 염두하여 현 계산에서 제외하여야 한다. *

우리 방식대로 하면 i+1번째를 계산하는 시점에서, i+1번째의 잔여량을 알게 된다. 그 만큼을 i+2번째 계산에서 제외한다. 위 그림에서는 1개가 남음으로 i+2번째에서 1개 제외 후 나머지 1개에 대해서만 비용 2로 처리하고, 다음 반복문으로 넘어간다.

(4) 꼬리 질문, 만약 i+3의 값이 0이면 계산에 차질이 생기지 않나요?

차질은 생기지 않는다. 왜냐하면, i+3의 값이 0일 경우, i+2 번째의 잔여 라면을 후에 계산하든 현 계산에 포함하여 계산하든 계산 결과는 같기 때문이다.

3. 코드 소개 🔎

(1) Sudo Code

// 입력
N (공장의 개수)
arr (공장에서 구매해야할 라면의 개수)

while(index가 N보다 작을 때 까지) {
    index번 공장의 라면은 모두 비용 3으로 풀 매수

    index + 1번 공장에서는 최대 index 공장에서 소비한 라면 만큼 비용 2로 매수
    index + 1번 공장에 잔여 라면 기록 

    index + 2번 공장에서는 index+1번의 잔여라면만큼 미리 빼두고, 나머지 부분에 대해서 비용 2에 매수
    (이 때 2에 매수하는 부분이 index 번 공장에서 매수한 라면 개수를 넘으면 안된다.)
}

정답 출력

(2) 구현 코드

public class Main {
    /*
    * b18185 라면 사기 (small)
    * 0. 다행히 문제에서 제시한 (3칸 = 7개, 2칸 = 5개, 1칸 = 3)의 비용 조건은 모든 칸을 분리해서 생각해도
    *    비용 조건 별로 묶어서 계산한 경우와 차이가 없다. (이 점을 이용해 모든 칸을 분리해서 생각한다.)
    *
    * 1. 현재 조회 중인 공장을 i라고 할 때, i 공장에서 될 수 있는 한 많이 사간다. max*3;
    *
    * 2. i+1과 i+2 공장의 경우, i의 라면 개수 만큼 이어져 있는 것이다.
    *       따라서 i의 라면 개수만큼 최대한 가져간다. (각 공장 별 라면 개수 * 2)
    *
    * 3. 다만 1211처럼 (0101 -> 0001 -> 0000)이 되는 것보다, (0111 -> 0000) 이 되는 것이 비용이 더 적을 수 있음
    *    따라서 2번에서 무작정 (조건 3 최대한 많이 -> 조건 2 최대한 많이) 로 이어져서는 안된다.
    *
    *    따라서 i, i+1, i+2 관계에서 i+1번의 라면 개수가 i+2보다 클 경우,
    *       2번 조건으로 했을 때, 남아있을 i+1 의 잔여 라면량 만큼 i+2의 라면도 살려둔다.
    *       만약 i + 3에 라면이 있다면 i+1부터 조건 3을 사용하면 되므로 최적의 효율을 낸다.
    *       i+3 공장의 라면 개수가 0이더라도, 남은 라면을 조건 2로 세면, 조건 3부터 Greedy 한 것과 비용이 동일
    *
    * */
    public static void main(String[] args) throws IOException {
        int ans = 0;
        int N;
        int [] arr;
        int idx = 0;


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int [N+2];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        while (idx < N) {
            int first_consume = arr[idx];
            int sec_consume = 0;
            int third_consume = 0;
            if(first_consume > 0) {
                ans += first_consume*3;
                arr[idx] = 0;

                sec_consume = Math.min(first_consume, arr[idx+1]);
                if(sec_consume == 0) continue;
                ans += sec_consume*2;
                arr[idx+1] -= sec_consume;
                // 현 시점에서 3번째 칸을 얼마나 소비할지.
                //      - 첫번째 라면양만큼(Maximum),
                //      - 두번째 남은 라면량만큼 남기고 전부 소비
                //      - 두번째 남은 라면량이 3번째 라면량을 초과하면, 아무것도 소비하지 않음.
                third_consume = Math.min(sec_consume, arr[idx+2] - Math.min(arr[idx+1],arr[idx+2]));
                ans += third_consume*2;
                arr[idx+2] -= third_consume;
            }
            idx++;
        }
        System.out.println(ans);
    }
}

4. 배운 것들 🎯

다이아 생각보다 할 만 한데?