백준 2217 로프 풀이 python, java

문제로이동

2217번: 로프

---

목차

 

---

---

문제 설명

그리디 문제는 규칙을 파악하는게 중요합니다.

• 로프 여러개를 사용해 병렬로 무게를 들 수 있습니다.
  • 이 때, W/K(갯수) 만큼의 무게가 걸리게 됩니다.
  • 즉, {나를 포함한 나보다 무게가 큰 로프 수 * 내 로프 = 최종 무게}가 성립됩니다.

1

5

3

2

4

이렇게 입력되었다고 가정하면 이 Array를 정렬해 줍니다.

 

 

5

4

3

2

1

내림차순이 편하긴한데, 오름차순도 index 접근값만 바꿔주면 되기 때문에 크게 상관없습니다.

자, 이제 각 Array에 (i+1)을 곱해줍니다.

 

5 * 1

4 * 2

3 * 3

2 * 4

1 * 5

이 Array중 최대값이 정답이 됩니다. 이 Array에서는 3*3인 9가 정답이겠네요.

선택하자면 3, 4, 5 로프가 사용되었고 1, 2 로프는 사용되지 않았습니다.

---

소스 코드

두 언어 모두 같은 로직인데 정렬이 오름차순이냐 내림차순이냐의 차이로 index 접근 방법이 살짝 다릅니다.

- 로프 값을 배열(list)로 입력받습니다.

- 로프를 정렬합니다.(Python은 내림차순, Java는 오름차순)

- 각 배열에 현재 index(크기 등수)를 곱해줍니다. (가장 큰 값은 1, 가장 작은 값은 n-1)

- 그 값 중에서 가장 큰 값을 출력합니다.

Python

import sys
input = sys.stdin.readline
n = int(input())
arr= list()
for _ in range(n):
    arr.append(int(input()))
arr.sort(reverse=True)
for i in range(n):
    arr[i] = arr[i]*(i+1)
print(max(arr))

---

Java8

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

public class Main {	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] arr = new int[n];
		for(int i = 0 ; i<n;i++)
			arr[i]=scan.nextInt();
		Arrays.sort(arr, 0,n);
		for(int i = n-1;i>=0;i--) {
			arr[i] = arr[i]*(n-i);
		}
		Arrays.sort(arr, 0,n);
		System.out.println(arr[n-1]);
	}
}