BOJ : 2217

💡문제 분석 요약

그리디 알고리즘 문제로 거의 공식만 찾아낸다면 풀 수 있는 문제라고 생각했다. 정렬을 해주게 되면 어차피 작은수를 작은수부터 가장 큰수까지 개수만큼 곱해주면 최대 무게라는 것이 나오기 때문에 비교만 해주면 된다.

💡알고리즘 설계

1. 로프의 개수, 로프 최대 무게를 배열로 받는다.
2. 로프의 무게가 들어있는 배열을 정렬한다.
3. 정렬한 후 0번 인덱스 값에 arr.length-i 를 곱해 변수에 저장한다.
4. 다음 인덱스부터 나오는 값들을 비교해 max에 넣는다.
5. max값을 출력한다.

💡코드

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

public class Q2217_boj {
    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];
        int weight = 0;
        int max = 0;

        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        for(int i=0;i<N;i++){
            weight = arr[i] * (N - i);

            if(max<=weight){
                max = weight;
            }
        }
        System.out.println(max);
    }
}

💡시간복잡도

O(N)

입력받은 N만큼만 연산함

💡 틀린 이유

하.. 예시 입력을 정렬한 상태로 넣어서 정렬을 안해버렸음요 그래서 정렬 코드만 추가해서 바로 돌렸습니다.

💡 틀린 부분 수정 or 다른 풀이

• 다른 풀이이사람은 배열 정렬을 뒤집어서 했으며, math 메서드를 사용하니 훨 간단해졌다. 어제 사용하기로 해놓고 또 안했네
•  

import java.io.*;
import java.math.BigInteger;
import java.util.*;

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());
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());  //수 입력받기
        }
        Arrays.sort(arr, Collections.reverseOrder());  //내림차순으로 정렬하기
        int total = 0;
        for (int i = 0; i < n; i++) {
            total = Math.max(total, arr[i] * (i+1));
        }
        System.out.print(total);
    }
}

💡 느낀점 or 기억할정보

그리디 알고리즘 같은 경우 공식과 비교계산이 많은 편인데 알면서 왜 math 메서드를 사용하지 않을까?