자바(백준) 2217 로프

오답 노트 & 새로 알게 된 점

해당 문제는 원리만 떠오르면 쉽게 풀 수 있는 문제인 것 같다.

 

나는 처음에 주어진 중량 중에 최솟값 * 로프의 개수와 주어진 주어진 중량 중에 최댓값을 구하고 최댓값을 가지는 로프의 개수를 구하여 Math.max(최솟값 * 로프의 개수, 중량 최댓값 * 최댓값을 자기는 로프의 개수) 로 구했다.

 

그러나 해당 반례를 통해 쉽게 틀렸습니다가 나왔다. 

3

10 

20

30

을 입력하면 답은 40이 나와야 한다. 그래서 이 반례를 보고 생각을 했다. 

 

아마 문제에서는 중량 순으로 줄을 입력해주지 않기 때문에, 일단 오름차순으로 정렬을 한다. 그리고 뒤에서부터 

해당 로프의 중량에서 개수를 곱한 값과 그 앞의 로프의 중량에서 개수를 곱한 값을 비교하였다.  

이렇게 비교할 수 있는 이유는 오름차순으로 정렬하였기 때문에 앞(index가 1 작은 거)의 로프의 중량이 무조건적으로 작다. 그래서 비교할 수 있다.

 

다시 한 번 말하면

앞 로프의 중량 * ( 자신을 포함한 이때까지 로프 개수)   ,      현재 로프의 중량 * (자신을 포함한 이때까지 로프 개수)

의 최댓값을 구하여 index가 0이 될 때까지 진행한다. 그렇게 되면 result가 나오게 된다.

---

코드

import java.io.*;
import java.util.*;
 
public class Main {
    /*
    k개의 로프에 중량 w 물체 올릴 때 각각 w/k만큼
    로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량
    1. 모든 로프를 사용해야할 필요 X 임의로 몇 개의 로프를 골라서 사용가능
     */
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int num = c(st.nextToken());
        int rope[] = new int[num];
        for(int i = 0; i < num; i++){
            st = new StringTokenizer(br.readLine());
            int value = c(st.nextToken());
            rope[i] = value;
        }
 
        Arrays.sort(rope);
 
        int result = 0;
        for(int i = num -1; i > -1; i--){
            rope[i] = rope[i] * (num - i);
            if(rope[i] > result) result = rope[i];
        }
        System.out.println(result);
    }
    static int c(String str){
        return Integer.parseInt(str);
    }
}