[백준] 알고리즘 분류(그리디 알고리즘,JAVA)2217번, 로프

문제 링크

 

2217번: 로프

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 로프들을 병렬로 사용하여 무게를 고르게 분산할 수 있습니다.

2. 주어지는 로프를 모두 사용할 필요는 없습니다.

3. 로프를 이용하여 들 수 있는 가장 큰 무게를 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 로프들을 정렬하여 각 로프가 가장 가벼운 중량일 때 비교합니다.

 

3. 모두 비교하였을 때 최대 들 수 있는 무게를 결과로 출력합니다.

 

로프 무게 비교하기.

 

로프들을 사용할 때 가장 가벼운 로프를 기준으로 들 수 있는 최대 무게를 구하실 수 있습니다.

 

무게를 높일수록 한계에 가장 먼저 도달하는 것은 가장 가벼운 로프이기 때문입니다.

 

예를 들어 로프 5와 10짜리를 병렬로 사용한다고 하면

 

들수 있는 무게는 : 1, 2 ... 10까지 들 수 있을 것이고 최대 무게는 10입니다.

 

점화식

 

가장 가벼운 로프 ×  최대로 사용한 로프의 개수

 

최대로 사용한 로프의 개수 = 가장 가벼운 로프보다 무거운 모든 로프의 개수

 

최대로 사용한 로프의 개수를 곱하는 이유는 무게를 최대한 분산시켜야 최대 무게를 구할 수 있습니다.

 

로프 5와 10을 점화식을 사용해보면

 

가장 가벼운 로프(5) × 최대로 사용한 로프의 개수(2개) = 10

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 2

로프의 무게 : 10 , 15

 

2. 로프들을 정렬하여 각 로프가 가장 가벼운 중량일 때 비교합니다.

 

로프의 무게 오름차순 정렬

 

로프의 무게 : {10, 15}

 

점화식 진행!

 

가장 가벼운 로프가 10일 때

 

가장 가벼운 로프(10) × 최대로 사용한 로프의 개수(2개) = 20

 

가장 가벼운 로프가 15일 때

 

가장 가벼운 로프(15) × 최대로 사용한 로프의 개수(1개) = 15

 

3. 모두 비교하였을 때 최대 들 수 있는 무게를 결과로 출력합니다.

 

15을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• Arrays.sort를 이용하여 로프의 정보가 저장된 배열을 정렬하였습니다.
• for문을 이용하여 각 로프가 가장 가벼운 로프가 되었을 때 점화식을 적용하였습니다.
• 모두 점화식을 적용한 뒤 최대 무게를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다

 

import java.io.*;
import java.util.Arrays;

public class Main{
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] num = new int[N];
        //로프 정보 저장
        for(int i=0;i<N;i++)
            num[i] = Integer.parseInt(br.readLine());
        Arrays.sort(num);		//로프 정보 오름차순 정렬
        int answer = Integer.MIN_VALUE;
        //모든 로프가 가벼운 로프가 되었을 때 점화식 진행
        for(int i=0;i<N;i++){
            int temp = num[i] * (N-i);
            answer = Math.max(answer, temp);	//무게 비교하기
        }
        bw.write(answer + "");	//최대 무게 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}