백준 18185번: 라면 사기 (Small)

 

18185번: 라면 사기 (Small)

처음에는 그리디 알고리즘 인줄알았다.

우선순위를 3번 -> 2번 -> 1번 순으로 처리하면 될 줄 알았지만,,,,

 

2322 인 경우를 생각해보자

 

그리디 알고리즘으로 풀 경우

2322 ->(14) 0102-> (3) 0002 -> (6) 0000 총 23의 값이 나온다.

 

best값은 무엇일까?

2322 ->(10) 0122 ->(7) 0011 -> (5) 0000 총 22의값

2322 -> (5) 1222 ->(7) 0112 -> (7) 0001 -> (3) 0000 총 22의값 인것을 알 수 있다.

 

즉, a[i + 1] > a[i + 2] 일 때는 a[i + 1] - a[i + 2]만큼의 차이와 a[i] 중 최솟값을 통해 2개의 공장에서 사는 경우를 먼저 처리해주고,

곧이어 바로 3개의 공장에서 구매할 수 있는 경우를 처리해준다.

if (inputArr[i+1] > inputArr[i+2]){
    int twoCase = Math.min(inputArr[i], (inputArr[i+1] - inputArr[i+2]));
    result += 5 * twoCase;
    inputArr[i] -= twoCase;
    inputArr[i+1] -= twoCase;

a[i + 1] - a[i + 2]보다 a[i]가 더 작을 때, 즉 a[i]가 0일 때 -> 7 * 0 = 0이므로 상관없다.

반복문을 사용하기 때문에 저런코드로 실행하다보면 ArrayIndexOutOfBoundsException예외가 발생할 수 밖에 없다.

우리는 i+1과 i+2의 문제만 있을테니까 

int[] inputArr = new int[count+2];
inputArr[inputArr.length -2] = 0;
inputArr[inputArr.length -1] = 0;

배열 크기를 2칸을 더 키워서 초기화를 시켜주었다.

• 위에 설명한 것 처럼 0 일때는 상관이 없기 때문이다.

전체적인 코드를 보면

package BJ10000;

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

public class BJ18185 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int count = st.countTokens();
        int result = 0;
        int[] inputArr = new int[count+2];
        inputArr[inputArr.length -2] = 0;
        inputArr[inputArr.length -1] = 0;

        if (N != count){
            System.out.println("2번째 입력을 다시해주세요 개수가 일치하지 않습니다.");
            System.exit(0);
        }
        for (int i = 0; i < count; i++){
            inputArr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < N; i++){
            if (inputArr[i+1] > inputArr[i+2]){
                int twoCase = Math.min(inputArr[i], (inputArr[i+1] - inputArr[i+2]));
                result += 5 * twoCase;
                inputArr[i] -= twoCase;
                inputArr[i+1] -= twoCase;

                int threeCase = Math.min(inputArr[i],inputArr[i+1]);
                threeCase = Math.min(threeCase,inputArr[i+2]);
                result += 7 * threeCase;
                inputArr[i] -= threeCase;
                inputArr[i+1] -= threeCase;
                inputArr[i+2] -= threeCase;
            }
            else {
                int threeCase = Math.min(inputArr[i],inputArr[i+1]);
                threeCase = Math.min(threeCase,inputArr[i+2]);
                result += 7 * threeCase;
                inputArr[i] -= threeCase;
                inputArr[i+1] -= threeCase;
                inputArr[i+2] -= threeCase;

                int twoCase = Math.min(inputArr[i], inputArr[i+1]);
                result += 5 * twoCase;
                inputArr[i] -= twoCase;
                inputArr[i+1] -= twoCase;
            }
            result += 3 * inputArr[i];
        }
        System.out.println(result);
    }
}

 

사실 내가 짠 코드는 if문 덕질되어 있어서 다른 사람들 코드를 살피다가.. 코드로 잘 설명해주셔 해결했다.

18185번 라면 사기 (Small)