강승현입니다
article thumbnail
반응형

문제로이동

 

2217번: 로프

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

www.acmicpc.net


목차

     



    문제 설명

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

    • 로프 여러개를 사용해 병렬로 무게를 들 수 있습니다.
      • 이 때, 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]);
    	}
    }
    
    반응형
    profile

    강승현입니다

    @CODe_

    포스팅에 대한 피드백을 환영합니다!
    피드백 작성자를 존중하며, 함께 공유하고 성장할 수 있는 기회가 되기를 기대합니다.의견이나 조언이 있다면 언제든지 자유롭게 남겨주세요!

    article prev thumbnail
    article next thumbnail
    profile on loading

    Loading...