BOJ_2217 : 로프

👉 문제링크

2217번: 로프

---

---

🔸 문제 분석 🔸

• 입력받은 로프로 들 수 있는 최대 중량을 출력한다.
• 최대 중량은 가장 약한 로프 * 로프의 개수 이다.

🔸 코드 🔸

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

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 arr[] = new int[n];
        for (int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);
        int answer = 0;
        for (int i = n-1; i >= 0; i--){
            int temp = arr[i] * (n-i);
            if (temp > answer) answer = temp;
        }
        System.out.println(answer);
    }
}

🔸 코드 해석 🔸

• n이 최대 100,000이고 각 로프의 중량은 최대 10,000 이므로, 최대 중량의 최대값은 100,000 * 10,000 = 1,000,000,000 (10억)이다. 따라서 int(최대 20억)를 사용해도 된다.
• 문제의 제한시간은 2초이고, 최소값을 사용해야 한다.
  • 매번 최소값을 구해줘야 하면, O(n^2) == 10,000,000,000으로 100억회 계산으로 약 100초가 소요된다.
  • 따라서 최소값을 따로 구해줄 필요가 없도록 정렬후 내림차순으로 계산한다.
• 오름차순 정렬 후 최대값을 찾는 반복문을 뒤쪽으로 순회한다.
  • 정렬했으므로 인덱스 i로 나오는 값은 항상 최소값이다.
  • (최소값 * 로프의 개수)의 최대값을 출력한다.

---

🔸 end 🔸

• 문제를 잘못 파악하고 DFS를 사용해야하나 한참 고민했다.
• 문제 태그가 정렬, 그리디인걸 보고서야 풀이를 파악할 수 있었다.
  • answer의 자료형을 일단 long으로 두고 맞았는데, 계산해보니 int로도 가능해서 바꿔주었다.
  • 정렬했으므로 (최소값 * 로프의 개수)가 한 번이라도 answer보다 작으면 뒤는 검사하지 않아도 되는 줄 알았다.
    • (최소값)이 너무 작아서 일시적으로 더 작게 나올 수 있지만, (로프의 개수)가 커지며 다시 최대값이 갱신 될 수 있으므로 전부 확인해야 한다.
• 혹시 풀이 초점이 틀렸을까 해서 다른 풀이들을 확인해봤었지만, 위의 이유때문에 틀린거였다.