[백준 2217번] 로프

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

2217번: 로프

 

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

2
10
15

예제 출력 1 복사

20

 

문제 분석

1. 입력받은 로프 오름차순 정렬

2. 첫번째 로프 * n = 들어 올릴 수 있는 최대 중량(answer)

   if(answer < 첫 번째 이외 루프) 가장 끝에 있는 루프 출력

 

실패 코드

package greedy;

import java.util.*;
public class Rope {

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = kb.nextInt();
		}
		Arrays.sort(arr);
		// 결과
		int answer = arr[0] * n;
		for(int i=0; i<arr.length; i++) {
			if(answer < arr[i]) {
				answer = arr[n-1];
				break;
			}
		}
		System.out.println(answer);
	}

}

어디가 틀렸을까? ...... 

 

구글 서칭을 하다가 어느 한 분이 예제를 추가하신 것을 보았습니다. 그것을 바탕으로 코드 수정을 해보겠습니다.

예제 많이 넣어주라ㅠㅠ 삽질 내가 할게... 대신 어디서부터 어디까지 삽질해야 할지는 알려주셨으면...

 

[불특정 인물이 추가한 예제]
5
35
33
30
20
12

이 경우 제가 코드 구현한 것을 토대로 나온 60이 아닌 90입니다.

 

어떻게 해서 90이 나왔는지 분석해보고 코드로 옮겨서 구현해보겠습니다.

 

문제 마지막 줄에 '모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.'라는 문구가 있습니다. 

 

내림 차순으로 정렬 후

[35, 33 ,30, 20, 12]

 

앞에서 부터 하나씩 뽑아서 비교해보자면,

1) 중량35을 꺼내면,  이 로프를 이용하여 들어 올릴 수 있는 물체의 최대 중량은 35입니다.

2) 중량33, 35을 꺼내면,  이 로프들을 이용하여 들어 올릴 수 있는 물체의 최대 중량은 33*2 = 66입니다.

3) 중량30, 33, 35을 꺼내면, 이 로프들을 이용하여 들어 올릴 수 있는 물체의 최대 중량은 30*3 = 90입니다.

4) 중량20, 30, 33, 35을 꺼내면, 이 로프들을 이용하여 들어 올릴 수 있는 물체의 최대 중량은 20*4 = 80입니다.

5) 중량12, 20, 30, 33, 35을 꺼내면, 이 로프들을 이용하여 들어 올릴 수 있는 물체의 최대 중량은 12*5 = 60입니다.

 

이 중에서 제일 최대 중량이 큰 병렬연결은 30, 33 ,35인 90입니다.

 

이 내용을 반영해서 코드 구현해보자면,

import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		Integer[] arr = new Integer[n];
		for(int i=0; i<n; i++) {
			arr[i] = kb.nextInt();
		}
		Arrays.sort(arr, Collections.reverseOrder());
		// System.out.println(Arrays.toString(arr)); [35, 33, 30, 20, 12]
		
		// 임시 변수 : 최대 중량 지속적으로 갱신
		int tmp = arr[0];
		for(int i=0; i<arr.length; i++) { 
			arr[i]  = arr[i] * (i+1); 
			if(tmp < arr[i]) tmp = arr[i];
		}
		System.out.println(tmp); 
	}

}

 

 

 

배열 정렬하는 포스팅을 추가하였습니다.

특히 내림차순에서 막히셨다면 가볍게 한 번 보고 오시는 것을 추천합니다.

배열 오름차순, 내림차순 정렬하기

배열 오름차순, 내림차순 정렬하기