[백준 2217] 로프 - JAVA

안녕하세요 놀이방사장입니다.

 

이번 포스팅은 백준 

2217 "로프"

문제 풀이입니다.

 

2217번: 로프

 

문제설명

K의 개의 로프가 주어줍니다.

각 로프의 사양은 주어집니다.

로프를 이용해 들 수 있는 최대 무게를 구하는 문제입니다.

모두 고르게 중량이 걸린다고 적혀있습니다.

 

이 뜻은 위에 예제로 예시를 들면

10,15 두개를 같이 사용하면 저기서 제일 낮은 수의 10 * (로프의개수) 가 최대중량입니다.

15를 혼자 쓸 경우 15가 최대 중량이라는 뜻입니다.

 

그래서 무조건 로프를 많이 쓴다고 들 수 있는 최대 중량이 느는 게 아닙니다.

ex ) 10 25 75 로프가 주어집니다.

여기서 3가지 다 봅니다.

10 25 75 쓸 때 (10 * 3 ) = 30

25 75 쓸 때 (25 *2) = 50

75 쓸 떄 = (75*1) = 75

이럴 떄는 75짜리 로프 하나쓰는 게 최대중량을 들 수 있습니다.

 

 

이걸 코드로 구현 해줍시다

/*
    백준 2217 로프
* */
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

public class Main{
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
        ArrayList<Integer> arr = new ArrayList<>();
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i<n; i++){
            arr.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(arr);
        int max = 0;
        int cnt = 0;
        int arrLen = arr.size();
        for(int i = 0; i<arrLen; i++){
            int tmpMax = (arr.get(i) * (arrLen-cnt));
            cnt++;
            if(tmpMax > max){
                max = tmpMax;
            }
        }
        System.out.println(max);
    }
}

먼저 ArrayList에 로프의 각각 최대중량을 추가해줍니다.

그리디 방법을 이용해서 가벼운 중량 * 가지고있는 로프수

그 후 에는 두 번째로 가벼운 중량 * (가지고 있는 로프수 - 두번째로 가벼운 중량보다 더 작은 중량을 들 수 있는 로프의 수)

반복하여 최대 중량을 찾는 코드입니다.

 

더 궁금하신 점이 있으시면 댓글남겨주세요

 

감사합니다.