[코딩테스트] 백준 자바 11399번

오늘은 백준 11399번 문제를 포스팅하겠다.

 

바로 들어가보자. 🔥

 

---

백준 문제 보기

백준 문제

 

그리디 알고리즘 유형의 문제로

생각보단 간단하게 풀 수 있다.

 

바로 설명으로 들어가보자. 😊

 

---

우선 문제를 보자마자

그리디 알고리즘의 핵심인 '정렬'을 해야

최소 시간을 구할 수 있을 것이라 생각해

두번째 줄 입력값을 arr에 대입했다.

 

그리고선 합계를 구해야하는데

예시

 

다음을 예시로 들면

배열을 정렬하면

1 2 3 3 4가 될 것이고

첫번째 사람은 1분을

두번째 사람은 1+2분을

세번째 사람은 1+2+3분을

네번째 사람은 1+2+3+3분을,,

다섯번째 사람은 1+2+3+3+4분을 기다려야한다.

 

쉽게 말해 

(arr[0] * 5) + (arr[1] * 4) + ... + (arr[4] * 1)이 합계가 된다!!

 

 

(arr[0] * 5) + (arr[1] * 4) + ... + (arr[4] * 1)

이 식을 좀 더 일반화해보자.

 

N = 5이므로 i를 1씩 증가시키면서 5번 반복시키고

sum+=arr[i] * (N-i)를 해주면 된다!!

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

 

이 부분만 이해했다면 별다른 어려움 없이

문제를 풀어낼 수 있었을 것이다.

 

---

그럼 이제 전체 코드를 보자. 

 

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

public class Q11399 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int arr[] = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);


        // 배열 정렬했으면
        // arr[0] 5번 + arr[1] N-1번 + arr[N-1] 1번 더하기
        int sum = 0;
        for(int i=0; i<N; i++) {
            sum+=arr[i] * (N-i);
        }
        System.out.println(sum);
    }
}

위에 설명한 합계 구하는 식만 이해된다면

별다른 어려움 없이 해결할 수 있을 것이다.

 

---

 

다음으로 실행결과를 보자. 

실행결과

 

---

아직 그리디 알고리즘의 문제를

많이 풀어본 것은 아니지만

그리디 알고리즘 문제를 보면

'최적'을 구하기 위해선 '정렬'을 해야한다는 핵심은 알겠다!!

 

그럼 더 열심히 공부하자. 🔥