문제 설명
그리디 문제는 규칙을 파악하는게 중요합니다.
- 로프 여러개를 사용해 병렬로 무게를 들 수 있습니다.
- 이 때, 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]);
}
}