[구름톤 챌린지, Java] 15일차, 과일 구매(그리드)

문제 링크

구름LEVEL

---

접근 방법

이 문제에 핵심

1. 종류가 N개인 과일이 존재하며, 각 과일에 가격과 포만감이 존재합니다.

2. 과일을 조각내서 구매할 수 있으며, 조각되었을 때 포만감은 "포만감 ÷ 가격" 입니다.

3. 플레이어는 K만큼 돈을 가지고 있을 때 최대 포만감을 결과로 출력합니다.

4. 가격은 항상 포만감의 배수입니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 모든 과일을 가격 1로 조각 내었을 때, 포만감이 큰 값부터 구매를 진행합니다.

 

3. 구매가 종료되었을 때 얻은 포만감을 결과로 출력합니다.

 

 

구현

 

모든 과일을 가격 1로 조각 내었을 때 포만감을 구합니다.

 

예를 들어.

 

	과일1	과일2	과일3	과일4
(가격, 포만감)	(1, 5)	(3, 6)	(2, 12)	(5, 40)

 

	과일1	과일2	과일3	과일4
개수 당 포만감	5 ÷ 1 = 5	6 ÷ 3 = 2	12 ÷ 2 = 6	40 ÷ 5 = 8

 

가격 1일 때 포만감을 기준으로 표를 표현하면

포만감	8	6	5	2
조각 개수	5	2	1	3

 

이제 K = 6일 때 최대 포만감을 구하면

 

조각당 포만감이 제일 높은 8부터 최대한 사용합니다.

 

포만감 8인 조각 모두 사용!!

 

포만감 : 8 × 5 = 40

 

남은 무게 : 6 - 5 = 1 

 

다음으로 큰 포만감이 6인 조각 사용!!

 

포만감 : 6 × 1 = 6

 

남은 무게 : 1 - 1 = 0

 

※ "조각의 개수 ≤ 현재 구매 가능한 무게" 가 성립할 때에는 모든 조각을 구매할 수 없으므로 현재 구매 가능한 무게만큼만 조각을 구입합니다.

 

→ 그래서 포만감 6인 조각은 모두 2개이지만, 남은 구매 금액이 1이기 때문에 1개만 구입을 진행하였습니다.

 

모든 구매가 종료되었습니다.

 

지금까지 얻은 포만감 : 40 + 6  = 46

 

최대로 얻을 수 있는 포만감 : 46으로 구할 수 있습니다.

 

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 6

 

K : 13

 

	과일1	과일2	과일3	과일4	과일5	과일6
(금액, 포만감)	(2, 8)	(7, 35)	(1, 5)	(3, 12)	(10, 30)	(1, 7)

 

2. 모든 과일을 가격 1로 조각 내었을 때, 포만감이 큰 값부터 구매를 진행합니다.

 

모든 과일을 조각 내었을 때

	과일1	과일2	과일3	과일4	과일5	과일6
개수 당 포만감	8 ÷ 2 = 4	35 ÷ 7 = 5	5 ÷ 1 = 5	12 ÷ 3 = 4	30 ÷ 10 = 3	7 ÷ 1 = 7

 

 

포만감	7	5	4	3
조각 개수	1개(과일6)	8(과일2, 과일3)	5(과일1, 과일4)	10(과일5)

 

조각당 포만감이 제일 높은 7부터 최대한 사용합니다.

 

포만감 7인 조각 모두 사용!!

 

포만감 : 7 × 1 = 7

 

남은 무게 : 13 - 1 = 12 

 

다음으로 큰 포만감이 5인 조각 사용!!

 

포만감 : 5 × 8 = 40

 

남은 무게 : 12 - 8 = 4

 

다음으로 큰 포만감이 4인 조각 사용!!

 

포만감 : 4 × 4 = 16

 

남은 무게 : 4 - 4 = 0

 

※ "조각의 개수 ≤ 현재 구매 가능한 무게" 가 성립

 

3. 탐색이 끝났을 때 방문한 노드와 마지막 노드를 결과로 출력합니다.

 

구매한 조각들의 포만감 합

 

7 + 40 + 16 = 63

 

63을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 띄어쓰기 기준 입력값을 나누었습니다.
• 금액과 포만감을 기준으로 금액 1이 될 때 조각의 정보를 구해서 TreeMap에 저장합니다.
• 조각의 포만감이 가장 큰 것부터 구매를 진행합니다.
• 구매가 종료된 뒤 얻은 포만감의 합을 결과로 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

 

결과코드

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st =  new StringTokenizer(br.readLine()," ");
        //입력값 저장
        int N = Integer.parseInt(st.nextToken());
        long K = Long.parseLong(st.nextToken());
        //포만감 기준 내림차순 정렬을 위한 TreeMap
        TreeMap<Integer, Long> map = new TreeMap<>(Collections.reverseOrder());
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            int w = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            //가격이 1이 되도록 과일 조각 내기
            int idx = p/w;
            if(map.containsKey(idx)){	//기존에 있던 포만감일 때
                map.put(idx,map.get(idx) + w);
            }else{		//기존에 없던 포만감일 때
                map.put(idx, (long) w);
            }
        }
        //최대 포만감부터 조각 구입하기
        long result = 0;
        for(int key : map.keySet()){
            long cnt = map.get(key);
            //조각의 개수 ≤ 현재 구매 가능한 금액
            if(K - cnt <= 0){
                result +=  key * K;
                break;
            }
            //모든 조각 구매!
            result += key * cnt;
            K -= cnt;
        }
        //구매를 통해 얻은 포만감 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}

 

---

느낀 점

 

문제를 풀 때 입력값의 범위를 제대로 파악하지 않고 int형으로 사용하면서 오버플로우가 발생하여 문제가 계속 틀렸습니다.

 

로직은 올바르게 작성했다고 판단하였지만, 입력값 범위를 제대로 확인하지 못한 제 자신에게 화가 났습니다.

 

다음부터는 입력값 범위를 자세히 살펴봐야겠다는 가르침을 얻게 되었습니다.