Softeer - 금고털이

---

 

처음에는 전체 조회를 통해 최대값을 찾고 더해주는 식으로 했는데 2초가 넘는 결과가 있었다.

	public static void re() {
        int sumweight=0;
        int maxpoint=0;
        int result=0;
		
        while(sumweight<bag){
       	 int maxprice = -9999999;
            for(int i=0; i<repeat; i++){
               if(maxprice<array[i][1]){
                   maxpoint=i;
                   maxprice=array[i][1];
               }
            }
            if(array[maxpoint][0]+sumweight<bag){
                sumweight=array[maxpoint][0]+sumweight;
                result = result+(array[maxpoint][0]*array[maxpoint][1]);
                array[maxpoint][1]=0;
            }else if(array[maxpoint][0]+sumweight>=bag){
                result = result+((bag -sumweight)*array[maxpoint][1]);
                break;
            }


       }
       System.out.println(result);
	}

2차배열을 정렬 해주는 방법을 찾아보았다.

1. 2차배열 정렬

Arrays.sort(array,Comparator.comparingInt(o1->o1[0]));

o1은 배열의 element를 나타낸다. 나는 두번째 값을 비교하고 싶음으로 o1->o1[1] 로 바꿔줬다.

하지만 결과는 오름차순이기 때문에 내림차 순으로 바꿔줘야 했다.

2. 오름차순

Arrays.sort(array,Collections.reverseOrder());

위와 같이 오름차순으로 할 수 있다. 2개를 합치면 다음과 같이 된다.

Arrays.sort(array,Collections.reverseOrder(Comparator.comparingInt(o1->o1[1])));

 

 

 

전체소스

package test;

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

public class Main {
	static int[][] array;
	static int bag;
	static int repeat;

	public static void re() {
		int sumweight = 0;
		int i = 0;
		int result = 0;

		while (sumweight < bag) {

			if (array[i][0] + sumweight < bag) {
				sumweight = array[i][0] + sumweight;
				result = result + (array[i][0] * array[i][1]);
				array[i][1] = 0;
			} else if (array[i][0] + sumweight >= bag) {
				result = result + ((bag - sumweight) * array[i][1]);
				break;
			}

			i++;
		}
		System.out.println(result);
	}

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

		bag = Integer.parseInt(st.nextToken());
		repeat = Integer.parseInt(st.nextToken());

		array = new int[repeat][2];

		int price;

		for (int i = 0; i < repeat; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			array[i][0] = Integer.parseInt(st.nextToken());
			array[i][1] = Integer.parseInt(st.nextToken());

		}
		// Arrays.sort(array,Collections.reverseOrder());
		Arrays.sort(array, Collections.reverseOrder(Comparator.comparingInt(o1 -> o1[1])));

		re();

		br.close();

	}
}

 

 

 

---

문제

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

 

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

 

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

제약조건

1 ≤ N ≤ 106인 정수

1 ≤ W ≤ 104인 정수

1 ≤ Mi, Pi ≤ 104인 정수

입력형식

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

출력형식

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

입력예제1

100 2 90 1 70 2

출력예제1

170