h.o.Algorithm | Java | 백준 9329 - 그리디 - 효율치를 활용한 Greedy 문제 해결

백준 9329 문제를 분석하는 글이다.

h.o.Algorithm - 효율치를 이용한 Greedy 문제해결

문제

ACM-ICPC 아시아 지역 대회기간 중 대전의 패스트 푸드 음식점들은 그들의 음식점을 홍보하기 위해 이벤트를 준비한다. 특정 음식을 먹을 때 마다 스티커를 하나 제공하는데 스티커를 모으면 상금으로 교환할 수 있다. 같은 종류의 스티커가 필요한 상금은 여러 번 교환할 수 있으며, 같은 종류의 스티커를 가진 서로 다른 액수의 상금은 존재하지 않는다. 상금 교환에 필요없는 스티커도 있다.지역대회를 보러 가면서, 당신의 코치가 패스트 푸드 음식점에서만 식사를 하도록 허락했을 때, 얼마나 많은 상금을 획득할 수 있을까?

문제 분석

문제를 분석하기 앞서 문제를 직관적으로 이해하기 위해 입력 데이터를 보면서 살펴보고자 한다.

2 10
3 1 2 3 100
4 4 5 6 7 200
2 3 1 4 5 2 2 1 3 4

• 2 10 : 2개의 쿠폰종류가 있고, 스티커의 종류가 10개이다.
• 3 1 2 3 100 : 3개의 스티커 (1, 2, 3)을 갖고 있을 때 쿠폰 100을 받을 수 있다.
• 4 4 5 6 7 200 : 4개의 스티커 (4, 5, 6, 7)를 갖고 있을 때 쿠폰 200을 받을 수 있다.
• 2 3 1 4 5 2 2 1 3 4 : 1번부터 10번까지 갖고 있는 스티커의 개수이다. (1-"2장", 2-"3장", 3-"1장", ... 10-"4장")

알고리즘 분석

Reward 클래스 정의

private static class Reward{
    int[] stickers;
    int value;

    Reward(int[] stickers, int value){
        this.stickers = stickers;
        this.value = value;
    }

    double getEfficiency(){
        return (double) value / stickers.length;
    }
}

• 각 쿠폰별로 Reward 클래스를 만들어서 객체로 다룰 것이다.
• 쿠폰별로 필요한 스티커의 개수가 달라 여러 쿠폰을 일관된 방식으로 처리하기가 쉽지 않다. 이럴 땐 일관된 방식으로 처리할 수 있는 한 차원 더 높은 클래스로 묶어주는 것을 고려해볼 필요가 있다.

Reward를 배열로 입력 후 정렬

// main()
Object[] inputs = input(br);
Reward[] rewards = (Reward[]) inputs[0];
int[] stickerCounts = (int[]) inputs[1];
Arrays.sort(rewards, (a, b)-> Double.compare(b.getEfficiency(), a.getEfficiency()));
  
private static Object[] input(BufferedReader br) throws IOException {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    Reward[] rewards = new Reward[n];
    for(int j=0; j<n; j++){
        st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int[] stickers = new int[k];
        for(int l=0; l<k; l++){
            stickers[l] = Integer.parseInt(st.nextToken());
        }
        int price = Integer.parseInt(st.nextToken());
        rewards[j] = new Reward(stickers, price);
    }
    st = new StringTokenizer(br.readLine());
    int[] stickerCounts = new int[m+1];
    for(int i=1; i<=m; i++){
        int sticker = Integer.parseInt(st.nextToken());
        stickerCounts[i] = sticker;
    }
    return new Object[]{rewards, stickerCounts};
}

• Reward 배열을 정렬할 때, getEfficiency()에 작성된 스티커장 쿠폰값을 사용했다. 가지고 있는 스티커의 수는 한정적이기 때문에 스티커당 값이 높은 쿠폰으로 교환해야 최대값을 기대할 수 있다.

Reward 연산

// main()
bw.write(execute(rewards, stickerCounts)+"\n");

private static long execute(Reward[] rewards, int[] stickerCounts) throws IOException{
    long totalReward = 0;
    for(Reward reward : rewards){
        int maxExchange = Integer.MAX_VALUE;
        for(int sticker : reward.stickers){
            maxExchange = Math.min(maxExchange, stickerCounts[sticker]);
        }

        totalReward += (long) maxExchange * reward.value;

        for(int sticker : reward.stickers){
            stickerCounts[sticker] -= maxExchange;
        }
    }
    return totalReward;
}

• 가지고 있는 스티커들 중 최대값을 찾아서 최대로 교환할 수 있는 쿠폰수를 구한다.
• Reward 배열은 정렬돼 있기 때문에, 스티커당 높은 쿠폰을 우선 고려하게 된다.
• 교환 후 남아있는 스티커 리스트에서 교환한 쿠폰수를 반영해준다.

중요한 점

• 스티커당 쿠폰값을 이용한다는 점을 기억해야 한다. 이렇게 했을 때 스티커 묶음 단위로 고려하던 쿠폰이 스티커당으로 바뀌어 문제를 직관적으로 이해할 수 있고 이후 비슷한 문제에서 활용할 수 있을 것으로 기대된다.