[백준BOJ] 2217번 로프.java

 

백준 저지에서 로프를 자바를 통해 풀어 보았다. 

 

https://www.acmicpc.net/problem/2217

2217번: 로프

2217번 로프.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

2217번 로프

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

설명

총 N개의 로프가 있으며 이 중 로프를 골라서 사용해야 한다. k개의 로프 위에 무게가 w인 물체를 올리면 각 로프들은 w/k만큼 중량이 걸린다. 각 로프들이 버틸 수 있는 무게는 다르다. 이 때 주어진 로프들을 사용해 들어올릴 수 있는 최대 무게를 구하는 문제이다.

 

임의로 로프 k개를 골랐다고 했을 때 견딜 수 있는 중량의 최대 무게는 로프 k개 중 가장 적게 견딜 수 있는 로프의 무게에 k를 곱한 값이다.

 

주어진 로프 중 어떤 로프를 선택하느냐에 따라 다른 결과가 나온다. 그래서 처음에는 부분집합으로 풀었는데 시간 초과에 걸렸다. 

 

그래서 그 다음으로는 주어진 순서대로 값을 비교해가며 다음 세 가지를 비교했다.

• 다음 로프가 최솟값이면서 포함되는 경우
• 다음 로프가 최솟값이 아니면서 포함되는 경우
• 다음 로프가 포함되지 않는 경우

위 세가지 중 가장 큰 값으로 갱신해가며 답을 구했는데 주어진 순서대로 구하는 것이기 때문에 최댓값을 구하지 못한다. 

 

상식적으로 최대 중량을 구하기 위해서는 더 많은 중량을 견딜 수 있는 로프를 먼저 선택하는 것이 맞다. 그래서 주어진 로프들을 내림차순으로 정렬한 뒤 위 과정을 다시 적용했다. 단 내림차순으로 정렬했기 때문에 다음 값은 이전 값보다 무조건 작기 때문에 포함되는 경우와 포함되지 않는 경우만 비교하면 된다.

코드

//2217번 로프.java
package week5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class 로프_2217 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    static int N;
    static Integer[] rope;
    static int answer = 0;
    static int minRope = Integer.MAX_VALUE;
	public static void main(String[] args) throws NumberFormatException, IOException {
		 N = Integer.parseInt(br.readLine());
		 rope = new Integer[N];
		 for(int i=0;i<N;i++) {
			 rope[i] = Integer.parseInt(br.readLine());
		 }
		 Arrays.sort(rope,Collections.reverseOrder());
		 
		 answer = rope[0];
		 for(int i=1;i<N;i++) {
			 answer = Math.max(answer, rope[i]*(i+1));
		 }
		 System.out.println(answer);
	}
}