[Softeer] Java - level2 문제풀이(금고털이)

 

 

softeer 금고털이(Java)

 

[문제]

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

 

[제약조건]

1 ≤ N ≤ 10^6인 정수

1 ≤ W ≤ 10^4인 정수

1 ≤ Mi, Pi ≤ 10^4인 정수

 

[입력형식]

첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.

 

[출력형식]

첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

 

[풀이]

귀금속의 가격을 배열의 인덱스로, 귀금속의 무게를 값으로 가지는 sortPrice 배열을 선언하는 것이 중요한 포인트이다.

제약조건의 price 범위가 10^4 이하인 정수인 점을 이용해 배열의 크기를 10001로 선언한다.

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

public class level2_1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] bag = br.readLine().split(" ");
        int W = Integer.parseInt(bag[0]);
        int N = Integer.parseInt(bag[1]);
        int[] weight = new int[N];
        int[] price = new int[N];
        int[] sortPrice = new int[10001];
        for(int i=0; i<N; i++) {
            String[] line = br.readLine().split(" ");
            weight[i] = Integer.parseInt(line[0]);
            price[i] = Integer.parseInt(line[1]);
            sortPrice[price[i]] = sortPrice[price[i]] + weight[i];
        }
        int totalPrice = 0;
        for(int i=10000; i>=0; i--) {
            if(sortPrice[i]>=W) {
                totalPrice += W * i;
                break;
            } else {
                totalPrice += sortPrice[i] * i;
                W -= sortPrice[i];
            }
        }
        System.out.println(totalPrice);
        br.close();
    }
}

 

실제로 쉽게 풀이한 것 같지만 수많은 실패를 거듭해서 나온 결과입니다.ㅎㅎ