[백준] 2217번: 로프(그리디, 수학)

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

2217번: 로프

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;

public class Main {

	public static void main(String[] args) throws IOException {
		//Scanner scan = new Scanner(System.in);
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(bf.readLine());
		Integer[] lope = new Integer[N];	// 각 로프 중량
		int maxWeight = 0;					// 최대 중량
		int num = 1;						// 로프 갯수
		for(int i=0; i<lope.length; i++) 
			//lope[i] = scan.nextInt();
			lope[i] = Integer.parseInt(bf.readLine());
			
		
		// 내림차순 정렬
		Arrays.sort(lope, Collections.reverseOrder());
		
		// 15*1 , 10*2, ... 비교
		for(int i=0; i<lope.length; i++) {
			maxWeight = Math.max(lope[i] * num, maxWeight);
			num ++;
		}
		
		bw.write(maxWeight + "\n");
		bw.flush();
		//System.out.println(maxWeight);
		//scan.close();
		bf.close();
	}

}

문제이해

문제 이해가 안되서 계속보고, 블로그도 찾아봤다.

문제에서 k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k만큼 중량이 걸리게 된다. 고 한다.

예제 입력1의 경우, 최대 중량을 보면

1개의 로프를 사용할 때 -> 최대 중량이 되려면 무게가 15인 로프 한개만 들어올릴때, 최대 중량은 15가 된다.

2개의 로프를 사용할 때 -> 최대 중량이 되려면 무게가 작은 10 * 2가 두개 들어올릴때, 최대 중량은 20이 된다.

 

만약 입력이 아래와 같다면,

4

35 10 20 30 

위 중량을 내림차순으로 정렬한다.

35 30 20 10

1개의 로프를 사용할 때 -> 최대중량은 35

2개의 로프를 사용할 때 -> 위 35로프랑 중량 30 로프랑 병렬로 연결해서 최대중량은 30 * 2 = 60이 된다.

3개의 로프를 사용할 때 -> 위 35, 30 로프랑 20로프를 병렬로 연결해서 20 * 3 = 60이 된다.

4개의 로프를 사용할 때 -> 위 35, 30, 20 로프랑 10로프를 병렬로 연결해서 10 * 4 = 40이 된다.

따라서 최대중량은 60이 된다.

 

풀이

위 이해한 내용을 바탕으로, 로프를 꺼내면서 병렬로 연결해서 최대 중량을 찾으면 된다.

 

 

※ 평소에 Scanner 클래스를 이용해서 입력을 받았는데, BufferedReader 클래스를 사용해서 입력받으니 메모리와 속도면에서 엄청 감소가 되었다.

가장 아래 - Scanner로 입력받기.

중간 - BufferedReader로 입력받기.

가장 위 - BufferedReader로 입력 + BufferedWriter로 출력하기.

 

Scanner와 BufferedReader의 메모리 & 시간에 있어서 상당한 차이가 있었다.

 

BufferedReader / BufferedWriter 알아보기