[백준] 18185번: 라면 사기 - JAVA

 

문제

 

풀이

구매를 하는 조건은 아래와 같다.

1. i번째 공장에서는 항상 3원에 구매한다.

2. i+1번째와 i+2번째 공장에서 구매할 경우 각각 2원의 추가 비용이 든다.

 

이를 이용해 구매할 때 가장 저렴하게 구매하는 방법은 i에서 라면을 구매할 때 최대한 i+1, i+2에서도 같이 라면을 구매하면 된다.

하지만 아래 반례로 i만큼 무조건 구매하는 방법으로는 해결할 수 없다.

4 2 3 2 1

 

만약 위의 방법대로만 풀이하게 된다면 비용이 20원이 된다.

2(구매)	3(구매)	2(구매)	1	7원
1(구매)	2(구매)	1(구매)	1	14원
0	1(구매)	0	1	17원
0	0	0	1(구매)	20원

 

그러나 19원의 비용으로 풀이하는 방법이 존재한다.

2(구매)	3(구매)	2(구매)	1	7원
1(구매)	2(구매)	1	1	12원
0	1(구매)	1(구매)	1(구매)	19원

 

이를 위해 추가해야할 조건은

i번째 공장을 방문할 때 i+1번째 공장에서 구매할 남은 라면의 개수가  i+2번째 공장에서 구매해야 할 남은 라면의 개수보다 더 많다면 i+2번째 공장에서 라면을 구매하지 않고 다음 차례로 넘긴다.

 

이 조건을 포함해 문제를 풀이한다면

 

0번째 공장(2개)에서 모든 라면을 구매한다. (2개 * 3 = 6원)

1번째 공장(3개)에서 0번째 공장에서 구매한만큼의 라면(3개) 중 구매할 수 있는 라면을 모두 구매한다. (2개 * 2 = 4원)

2번째 공장(2개)에서 1번째 공장의 원 보유량(3개)만큼의 라면을 구매한다. 만약 구매할 수 없다면 1번째 공장에서 현재 가지고 있는 라면(1개)만큼 남기고 구매한다. (1개 * 2= 2원)

따라서 0번째 공장에서 12원어치의 라면이 구매되고

0 1 1 1개의 라면이 남게 된다. 이후 1번째 공장에서 라면을 각각 구매하여 7원어치의 라면을 구매한다.

 

 

정답코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[] factory;
    static int money;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int 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());
        }

        int i = 0;
        while(i < N) {
            if(factory[i] > 0) {
                int temp = factory[i];
                // 구매할 수 있는 모든 라면 구매
                money += 3 * temp;
                // i에서 구매한 라면과 구매할 수 있는 라면 중 적은 수만큼 구매
                temp = Math.min(temp, factory[i + 1]);
                money += 2 * temp;
                // 구매한 라면만큼 마이너스
                factory[i + 1] -= temp;
                // i의 라면수와 i+2의 라면 수 - (i+1에 남은 라면과 i+2의 라면 중 적은 수) 중 적은 수만큼 구매
                temp = Math.min(temp, factory[i + 2] - Math.min(factory[i + 1], factory[i + 2]));
                money += 2 * temp;
                factory[i + 2] -= temp;
            }
            i++;
        }

        System.out.println(money);
    }
}

 

 

문의사항이나 피드백은 댓글로 남겨주세요.