[백준][JAVA] 13164 - 행복 유치원 - 그리디

📌 문제

백준 | 행복 유치원 | level5 | 그리디

https://www.acmicpc.net/problem/13164

 

 

📌 문제 탐색하기

• N명의 원생들을 키 순서대로 줄을 세우기
• 총 K개의 조로 나누려고 함
• 각 조에는 원생이 적어도 1명 있어야함
• 같은 조에 속한 원생들은 서로 인접해 있어야함
• 조별로 인원수가 같을 필요는 없음
• 조마다 티셔츠를 맞추는 비용 = 가장 키가 큰 원생 - 키가 작은 원생
• 출력 : 최대한 비용을 절약하기 위한 최소 비용

 

📌 알고리즘

• 원생의 수 N은 최대 300,000까지 가능
• K는 N이하
• 문제에서 이미 키 순서대로 작성됏으므로 Arrays.sort = O(NlogN)은 필요 x
• 출력값을 최소로 만들기 위해선, 처음부터 각 조의 가장 키가 큰 원생과 작은 원생의 차이가 작도록 구성해야함 ⇒ 그리디 !!
  • 1 기준 가장 차이가 안나는 3
  • 5 기준 가장 차이가 안나는 6
  • 10은 홀로 있으므로 10, 10 이여서 차이가 0

---

[첫 생각 방안]

1. n이 홀수일 경우, 가장 큰 값을 홀로 둠으로써 차이를 줄이는 것이 관건
2. ⇒ 이후, K-1개의 조를 지어야함
3. 짝수가 되면, k-1 또는 k개 안에서 조를 구성해야하므로…. (여기서 부터 막힘)

[두번째 생각 방안]

K개의 조로 만들어야한다면, 결국 끊는 조건은 K-1

가장 양 옆의 숫자 중에서 차이가 많이 나는 곳을 끊어야 최종 합을 줄일 수 있음

example)

1 3 5 6 10

1	3	5	6	10
(1-3사이 차이 : 2)	2	1	4

⇒ 이 중 가장 큰 2와 4 사이로 짤라야하므로, 남는 1+2 = 3 이 답이 된다.

 

 

📌 코드 설계하기

1. 입력값 변수에 대입
2. 각 사람들 사이의 차이 배열 생성
3. 이걸 Arrays.sort를 통해서 오름차순
4. 이후, k-1개로 차이가 큰 곳 제외, 나머지 위치들로 덧셈 진행

 

📌 정답 코드

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

public class Main {

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

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] people = new int[n];
        int[] sub = new int[n - 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            people[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < n - 1; i++) {
            sub[i] = people[i + 1] - people[i];
        }

        Arrays.sort(sub);
        int answer = 0;
        for (int i = 0; i < (n - 1) - k + 1; i++) {
            answer += sub[i];
        }

        System.out.println(answer);
    }

}

 

 

그리디.. 항상 풀 때마다 '코드' 풀이의 문제가 아니라, 어떻게 최적해를 구하는지 '그 로직을 떠올리는 것'이 더 문제인 것 같다.

앞으로 문제를 더 많이 풀어봐야하겠지만...

 

세이노 멘토님 왈, 최적해를 바로 고민하기 보단, 어떻게 하면 최적해에 가까워질 수 있을지를 고민해보면 도움일 될 것이라고 한다.

이 문제에서도 6과 10이 같은 조에 있으면 그 비용이 4로 급 커지는 것을 보면서, '이걸 어떻게 줄이지' 란 고민을 해야할 것 같다.