[코딩테스트] Java_ 백준 2217번 로프 (그리디 알고리즘) - Rowen Jobs

백준 2217번 로프 (그리디 알고리즘)

해당 문제는 신경쓸 부분이 조금 있어 시간이 걸렸다. 

*주의 내용*

1. 로프 전부를 사용할 필요 없다.

2. 최대중량을 고른다.

 

1. 받은 무게 중 최대 무게와 각 로프가 로프 갯수 비례하여 최대로 버틸수 있는 최대 무게를 비교한다.

2. 받은 무게 오름차순 정렬

3. 최소 로프를 하나씩 계산하고 로프 갯수를 하나씩 배어준다.

ex) 3개의 로프, 받은 무게 리스트 : 5, 10, 15 

로프의 갯수만큼 반복

첫번째 로프 : 5 * 3 = 15

두번째 로프 : 10 * 2 = 20

세번째 로프 : 15 * 1 = 15(비교할 최대 무게와 같아 계산 필요 없음)

로프 갯수를 줄이는 이유는 주의 내용 1번과 같다. 

 

받은 무게 최대 : 15 와 비교하여 최대 무게를 계산하면 20이 된다. 

 

로프 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

192 MB

57886

25434

20366

42.935%

문제

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

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

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

2
10
15

예제 출력 1 복사

20

출처

• 빠진 조건을 찾은 사람: bububu111
• 데이터를 추가한 사람: kdk8361
• 문제의 오타를 찾은 사람: roy752

알고리즘 분류

• 수학
• 그리디 알고리즘
• 정렬

 

코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
    	// 입력 셋팅
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        // 로프 갯수
        int line = Integer.parseInt(st.nextToken());
        int[] weight_list = new int[line];
        int real_max = 0;
		
        // 각 로프 버티는 무게 셋팅
        for(int i = 0; i < line; i++){
            st = new StringTokenizer(br.readLine());
            weight_list[i] = Integer.parseInt(st.nextToken());
        }
		
        // 버티는 무게 오름차순 정렬
        Arrays.sort(weight_list);
        
        // 최대 버티는 무게 구하는 반복문 실행
        for(int i = 0; i < line; i++){
        	// 주의1. line 이 하나일때 처리
            if(line != 1){
            	// 주의2. 마지막 line은 비교하지 않음 
                if((line - 1) != i){
                	// 무게 리스트 중 최댓값
                    int max = weight_list[line - 1];
                    // 무게 * 줄 갯수 = 해당 무게가 여러개의 줄과 있을때 최대 버틸수 있는 중량
                    int min = (line - i) * weight_list[i];
                    // 최댓값, 무게 * 줄갯수 최댓값 처리
                    if(real_max < min || real_max < max){
                        if(max > min){
                            real_max = max;
                        }else{
                            real_max = min;
                        }
                    }
                }
            }else{
            	// 무게 리스트 하나일 경우 최댓값 셋팅
                real_max = weight_list[0];
            }
        }
        System.out.println(real_max);
    }
}