[Java][2217] 로프

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

2217번: 로프

코드:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 각 로프가 버틸 수 있는 최대 중량
        int [] weight = new int[n];
		
        // 버틸 수 있는 최대 중량
        int maxW = Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            weight[i] = sc.nextInt();
            //로프를 1개만 쓴다고 가정했을 때 최대 중량은 무게 중 가장 큰 값
            // 따라서 max를 통해 가장 큰 값으로 설정함
            maxW = Math.max(maxW,weight[i]);
        }
		
        // 버틸 수 있는 중량 순 정렬
        Arrays.sort(weight);

	// 역순으로 로프 i개를 쓸 때 버틸 수 있는 최대 중량은
        // weight[n-i](뒤에서 i번 째)*i 임
        // for문을 계속 돌면서 maxW값 설정
        for(int i=1;i<=n;i++){
            maxW = Math.max(weight[n-i]*i,maxW);
        }

        System.out.println(maxW);


    }
}

 

for(int i=1;i<=n;i++){
    maxW = Math.max(weight[n-i]*i,maxW);
}

for문 예시)

로프 3개가 각각 5 10 15를 버틸 수 있을 때

weight[3-1]*1 즉 3번째 로프만 사용 했을 때 15를 버팀

weight[3-2]*2 즉 2,3번째 로프를 병렬로 사용 했을 때 각 로프가 버틸 수 있는 중량은
2번째 로프가 버틸 수 있는 중량은 20, 3번째 로프는 30까지 버틸 수 있음.
두 병렬로프가 최대 버틸 수 있는 중량은 (2번째 로프 기본중량)*로프 개수이므로 20

weight[3-3]*3 즉 1,2,3번째 로프를 병렬로 사용 했을 때 로프가 버틸 수 있는 최대 용량은
위와 같이 계산하여 10임

이를 점화식으로 바꾸면 n개의 로프가 있을 때 i개를 병렬 연결해 버틸 수 있는 최대 중량은
( (n-i)번째 로프 기본중량 ) * 로프 개수(i개) = weight[n-i]*i

(인덱스는 0부터 시작함 헷갈리지 않게 주의)