백준_13164 & 2212 (Greedy)

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

13164번: 행복 유치원

최근 본 코딩테스트에서 그리디 문제가 나왔는데 그리디 알고리즘 문제를 푼지 너무 오래돼서 제대로 못풀었다.

너무 분해서 다시 준비하려고 한다..

 

문제 자체는 간단하다.

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

N명의 수를 K개의 조로 구성했을 때 그 조에 속한 인원들의 키차이 합을 구하면 된다.

Greedy 알고리즘은 우리가 가진 모든 상황에 대해 최적의 해답을 찾아야한다.

 

이 문제에서 최적의 해답을 찾기 위해 필요한 요소들은 인접한 아이들의 키 차이이다.

그 모든 키 차이를 가지고 적절히 합해주면 답이 나오는 것이다.

 

K개의 조가 만들어져야 하니까 K-1개의 구분선이 생긴다.(3등분을 하려면 선 2개를 긋고, 2등분을 하려면 선 1개를 긋는것처럼)

 

만약 입력으로 주어진 N이 6이고 K가 2인 상황을 생각해보자. 그럼 다음과 같은 모습이 그려진다.

2개의 조, 키 차이는 11

 

2개의 조, 키 차이는 9 (1+8) 

 

2개의 조, 키 차이는 10 (4+6)

 

더 많은 경우의 수가 존재하지만 우선 여기까지만 보도록 하자.

 

지금 사진을 보면 결국 사용하게 되는 키차이는 위치만 다르지 결국 대부분 동일하다.

그리고 N-K개의 키차이만을 필요로 한다.

 

또한, 모든 경우의 수 중 최적의 해를 지닌 2번째를 보면 알겠지만 모든 학생들 사이의 키차이에서 N-K개의 최소값을 취하고 있다.

 

따라서

1. 모든 학생들 사이의 키 차이를 구하고, 

2. 해당 키 차이를 정렬하고

3. N-K개를 더해 필요한 값을 구한다.

=> 최적의해

 

package TT5_MAY;

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

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

        int n = Integer.parseInt(st.nextToken()); //인원
        int k = Integer.parseInt(st.nextToken()); //조

        st = new StringTokenizer(br.readLine());

        int[] kids = new int[n];
        for(int i=0;i<n;i++){
            kids[i] = Integer.parseInt(st.nextToken());
        }
        //1 3 5 6 10
        int[] result = new int[n];
        for(int i=1;i<n;i++){
            result[i] = kids[i]-kids[i-1];
        }
        Arrays.sort(result);
        for(int i=1;i<=n-k;i++){
            result[0] += result[i];
        }
        System.out.println(result[0]);
    }
}

 

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

2212번: 센서

이 문제도 똑같은 방식으로 풀면 된다.

package TT5_MAY;

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

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

        int n = Integer.parseInt(br.readLine()); //센서
        int k = Integer.parseInt(br.readLine()); //기지국

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] station = new int[n];
        for(int i=0;i<n;i++){
            station[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(station);
        ArrayList<Integer> al = new ArrayList<>();
        for(int i=1;i < station.length;i++){
            al.add(station[i] - station[i-1]);
        }
        Collections.sort(al);
        int sum =0 ;
        for(int i=0;i<n-k;i++){
            sum += al.get(i);
        }

        System.out.println(sum);
    }
}