[백준/JAVA] 2217번: 로프

🔺 문제

2217번: 로프

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int[] rope = new int[N];
        
        for(int i = 0 ; i < N ; i++) {
            rope[i] = Integer.parseInt(br.readLine());
        }
        
        Arrays.sort(rope);
        
        int max = Integer.MIN_VALUE;  
        for(int k = 0 ; k < N ; k++) {
            max = Math.max(max, rope[k] * (N - k));
        }
 
        System.out.println(max);
    }
}

✅ 해결 아이디어
✔ 그리디...
- 최대 무게 w = min(병렬 연결된 로프의 중량) * 병렬 연결된 로프 수
→ rope[k] * (N - k)

 

특정 로프를 사용할 경우, 그 로프보다 무게가 큰 로프를 모두 사용하는 것이 이득이므로 위와 같은 식을 활용한다.

 

예) [12, 20, 30, 33, 35]

• n = 0 일때 12 * 5 = 60 (12 20 30 33 35)
• n = 1 일때 20 * 4 = 80 (20 30 33 35)
• n = 2 일때 30 * 3 = 90 (30 33 35)
• n = 3 일때 33 * 2 = 40 (33 35)
• n = 4 일때 35 * 1 = 40 (35)

이 중 90이 제일 큰 값이므로, 이 값을 정답으로 출력한다.

 

---

🔺 다른 풀이들

- 악 이 분 글 보고 좀 이해했다...

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

 

 

- 입력받은 숫자 배열을 역순으로 정렬하고, 최대 중량을 (사용하는 로프 中 견딜 수 있는 중량이 가장 적은 로프) * (현재 사용하는 로프 수)로 설정한다. 반복문을 통해 사용하는 로프 수를 하나씩 늘리며 최대 중량을 갱신하는 풀이

백준 2217번 로프 (JAVA)

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

---

💬 느낀 점

w/k 저 식을 써야하나.. 싶어서 고민을 해보았는데

참고용이지 꼭 쓰이는 건 아니었다고 한다..

 

1회독	2회독	3회독	4회독	5회독
V	240416

---

(참고)

✔ 풀이 참고

[BOJ] 백준 2217번 : 로프 (JAVA)

백준 2217번 로프 (JAVA)