[백준-2217번 자바/java] 로프 _디버깅의 눈물

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

2217번: 로프

 

 

 

 

로프 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

192 MB

46100

20038

16101

42.689%

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

2
10
15

예제 출력 1 복사

20

 

 

 

 

---

 

 

체크 포인트

 

1. 그리디 알고리즘(Greedy Algorithm) 이용

 

-현재의 가장 최적의 답을 선택해 적합한 결과를 도출해내는 '그리디 알고리즘'을 이용하는 문제이다.

-그리디 알고리즘의 대표적 문제 유형으로는 활동 선택 문제나 거스름돈 문제 등이 있다.

 

-로프를 최소 1개 사용해서 다룰 수 있는 최대 중량을 출력하는 문제이다.

 

 

// 자체 예시

N:7

1
5
11
9
20
14
30

 

 

문제의 예시로는 경우가 잘 드러나지 않아 자체 예시를 들었다.

 

 

// 로프의 무게 오름차순 정렬
Arrays.sort(arr);

//  정렬 후 자체 예시
N:7

1
5
9
11
14
20
30

 

 

-우선 로프의 종류를 정렬해야한다. 가벼운 중량부터 무거운 중량을 다루는 순으로 로프를 오름차순 정렬(1, 5, 9, 11, 14, 20, 30 순)했다.

-이후 가장 무거운 중량을 다룰 수 있는 로프부터 탐색을 시작했다.

 

 

1)처음 로프는 30까지 다룰 수 있으므로 최대 중량(max)는 30이다.

 

2)두번째 로프는 20까지 다룰 수 있고, 첫 로프는 30까지 다룰 수 있지만 최대 중량은 40(20+20)이다.

왜냐하면 20이 넘어가는 순간 두번째 로프는 끊어지기 때문이다.

 

3)세번째 로프는 14까지 다룰 수 있고, 두번째 로프는 20, 첫 로프는 30까지 다룰 수 있지만 최대 중량은 52(14+14+14)이다. 왜냐하면 14가 넘어가는 순간 세번째 로프는 끊어지기 때문이다.

 

...

 

이 과정을 식으로 표현한다면 아래와 같다.

 

 

		// 다룰 수 있는 최대 중량이 무거운 로프부터 탐색
		for(int i=arr.length-1; i>=0; i--){
			// 현재 로프의 최대 중량과 새로운 최대 중량 비교
			max = Math.max(max, arr[i]*(N-i));
			
		}

 

 

 

 

 

 

 

 

풀이

 

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


class Main{
	
	static int max;
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 로프의 개수
		int N = Integer.parseInt(st.nextToken());
		
		// 로프의 종류를 담아주는 배열
		int[] arr = new int[N];
		
		for(int i=0; i<N; i++){
			st = new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		// 로프의 무게 오름차순 정렬
		Arrays.sort(arr);
		
		solution(N,arr);
		
		
	}// end of main
	
	
	
	static void solution(int N, int[] arr) {
		
		// 다룰 수 있는 최대 중량이 무거운 로프부터 탐색
		for(int i=arr.length-1; i>=0; i--){
			// 현재 로프의 최대 중량과 새로운 최대 중량 비교
			max = Math.max(max, arr[i]*(N-i));
			
		}
		
		// 최대값 출력
		System.out.println(max);
	}
	
	
	
} // end of Main