[Java] 2217. 로프

www.acmicpc.net/problem/2217

2217번: 로프

N개의 로프를 이용하여 들 수 있는 물체의 최고 중량을 구하는 문제이다.

N개의 로프를 이용하여 W의 중량을 들고자 할 때, 각 로프에는 W/N의 중량이 실리게 된다.

(이 문구를 보고 배열로 입력을 받고, (최솟값 * 배열의 개수)가 그 시점의 최대 무게라고 생각했다.)

 

전반적인 알고리즘 흐름은 다음과 같다.

 

1. 배열로 입력을 받아온다.

2. 현재 배열에서의 최솟값과 그 때의 배열의 길이를 곱해준다.

(이는 최솟값 * 배열의 길이를 그 시점에서 사용할 수 있는 로프를 이용한 최대 중량으로 구했다.)

3. 이를 새로운 배열에 저장한다.

4. 배열에서 최솟값을 지우고, 배열의 사이즈를 줄인다.

5. 2-4를 배열의 개수가 0 이상일 때까지 반복한다.

6. 그 당시 최대 무게를 저장한 배열에서의 최댓값을 구한다.

 

저의 경우에는 자바로 알고리즘 푸는 것이 익숙치 않아 파이썬으로 대략적인 큰 틀을 잡고 자바에서 로직을 이용해 다시 작성하고 있습니다. 파이썬의 경우에는 List를 이용하기 때문에 append 연산자를 이용하고, del 을 이용하여 사이즈를 조절할 수 있는 반면, 자바에서는 고정된 값을 갖는 배열을 사용하기에 부적합했습니다.

 

그래서 배열에서 최솟값을 삭제하는 방법이 아닌, 이와 비슷한 방법으로 Sorting 후 큰 수부터 1, 2, 3 ... 을 곱해나가고, 그 중 가장 큰 수를 답으로 도출해내는 방법을 이용하였습니다.

---

//1

arr 배열에 입력값을 받아온다.

 

//2

arr배열을 sorting한다. 내림차순으로 정렬이 가능하다면 생각하기 더 쉬웠을 것이라 생각한다.

 

//3

2번에서 내림차순으로 정렬했으면 하는 이유가 이것이다.

만약 내림차순이라면 배열의 인자들에 곱하는 인자를 (i+1)의 형태로 구할 수 있었을 것 같다.

 

//4

최댓값을 구하는 로직이다. 흔히 사용되는 로직을 사용했다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
        //1
		for (int i = 0; i < arr.length; i++) {
			arr[i] = sc.nextInt();
		}
        
        //2
		Arrays.sort(arr);

        //3
		for (int i = arr.length -1 ; i >= 0; i--) {
			arr[i] = arr[i] * (arr.length - i);
		}
        
        //4
		int max = Integer.MIN_VALUE;
		for(int k : arr) {
			if(max < k)
				max = k;
		}
		System.out.println(max);
		sc.close();
	}
}