[백준][JAVA][그리디 알고리즘] 2217 : 로프

 

문제

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

량이 서로 다를 수도 있다.

 

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

 

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오.

 

모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 단, 각각의 로프는 한 개씩만 존재한다.

 

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 정수이다.

 

출력

첫째 줄에 답을 출력한다.

728x90

 

세 번 풀어서 맞았는데 노트에 적은 풀이는 맨 처음에 푼 풀이이다.

(맨 처음에는 오름차순이랑 일부만 선택 가능하다는 옵션을 무시해버렸당ㅎㅎ)

 

지운 부분 밑으로는 내가 든 예시로 두 개로,

일단 오름차순으로 정렬해야 계산이 편해서

Array.sort(); 를 써서 로프 길이가 들어있는 배열을 정렬 했다.(자바 넘나 편한 것..)

 

그리고 병렬로 로프를 연결하기 때문에 로프마다 무조건 같은 중량이 걸리게 되는데,

이것만 알게되면 문제 풀이가 쉬워진다!

그리디 알고리즘은 강의 시간에 배우기만 했는데 실제로 써보니 그거슨 진짜 이론일 뿐이었다,,

(원래 이론이 더 복잡한 법이더라,,실제 활용이 더 중요한 거슬,,)

 

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan1=new Scanner(System.in);
        int n=scan1.nextInt(); //로프개수=n
        int[] temp1=new int[n];    //for문 내에서 임시로 매번 로프 길이를 입력 받을 변수
        int rope=0;    //로프 길이
        int num=0;    //arraylist temp2에서 가장 큰 중량을 가질 수 있는 로프의 인덱스
        ArrayList<Integer> temp2= new ArrayList<Integer>();
        //각 로프 선택 시 최대 중량을 저장할 arraylist
 
        for(int i=0; i<n;i++) temp1[i]=scan1.nextInt();
        //for문으로 n개의 로프 길이를 배열 temp1에 저장
        Arrays.sort(temp1); //오름차순 정렬
        //각 로프 선택 시 최대 중량을 temp2에 저장하고 가장 큰 중량의 인덱스를 num에 저장
        for(int i=0; i<n;i++) {
            temp2.add(temp1[i]*(n-i));
            if(temp2.get(i).intValue()>rope) {
                rope=temp1[i]*(n-i);
                num=i;
            }
        }
        int w=temp2.get(num).intValue();
        System.out.println(w);
    }
}http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

 

-1학년 2학기, 2학년 1학기 때 c언어1,2 강의를 들으면서 백준을 알게 됐는데

그 때는 뭐 풀기만 하면 자꾸 런타임 에러니 뭐니 하면서 실패했다고 해서 제대로 푼 기억이 없다.

(class이름은 Main으로 해야 채점이 되는데 그런 것도 그 때는 몰랐다ㅎㅎ )

그렇게 백준 문제랑 담 쌓고 살아서 였는지 2학년 2학기 끝나고 이번에 풀려고 들어가니까

막상 50퍼센트 정답률 문제도 틀릴까봐 풀기가 꺼려졌다ㅋㅋㅋ

근데 45퍼 정답률 문제를 맞추니까 괜히 자신감 생겨버리기,,

결론은 그냥 뭐,,더 열심히 해야겠다:-)!