자바(백준) 13164 행복 유치원

오답 노트 & 새로 알게 된 점

이 문제는 어려운 자료구조, 알고리즘을 사용하여 어려운 문제가 아닌, 나에게 너무나 논리적은 사고를 요하는 문제로서 정말 난이도가 높았다. 해당 문제를 푼 분들은 이러한 원리를 깨닫고 푼 것이면 정말 대단하다고 느꼈다. 

문제 설명을 듣고 이해했을 때 감명받고, 어려운 문제였다고 생각한다. 

해당 문제 설명은 오카방에서 여쭤봤고, 내가 기록한 모든 풀이들은 류호석(https://github.com/rhs0266/FastCampus)님께서 말씀해주셨다.. 너무 감사했다..

 

문제 풀이 순서

1. 1과 3, 3과 5, 5와 6, 6과 10의 차이를 diff배열에 넣는다.

2. 이것들을 오름차순하여 index가 [ 0, N-K ) 까지 더한다.

 

여기서 1번부터 보겠다.

난 어떤 원리로 1번과 같이 각각의 차이를 구하여 오름차순하여 더하면 최솟값이 나오나라는 의문이 들었다. 

문제에서 입력 값은 무조건 키순으로 되어있다고 했다. 그렇다면 어떻게든 그룹을 지어도 제일 왼쪽은 키가 제일 작은 학생, 제일 오른쪽은 키가 제일 큰 학생일 것이다. 그룹이 x번부터 y번 학생을 포함한다고 하고, 이걸 식으로 나타내면

arr[y] - arr[x] 일 것이다.

그렇다면 여기서 arr[y] - arr[x] 를 풀어서 써보면,

arr[y] - arr[x] = arr[y] + (- arr[y-1] + arr[y-1]) (- arr[y-2] + arr[y-2]) - … (- arr[x+1] + arr[x-1]) - arr[x]이다.

예로 [1, 2, 3, 4]가 한 그룹이면

4 - 1 = 4 - 3 + 3 - 2 + 2 -1

4 - 1 = 4  + ( - 3 + 3) + ( -2 + 2 ) - 1 이다.

그래서 모든 그룹의 비용을 합치는 건 그룹 안의 diff를 다 더한다는 뜻이다. 그니까 그룹이 어떻게 될 진 몰라도, 각각의 모든 diff를 더하게 되면 가장 큰 수에서 가장 작은 수의 뺄셈과 같다 이거다. 그래서 diff를 구하는 것이다.

 

---

 

2번을 보겠다.

왜 범위가 N-K 미만까지 일까?라는 생각이 들었다.

처음에 N 명이 각자 하나의 그룹이라고 생각하고 인접한(이 말이 중요한 것 같다) 그룹과 합친다.

1번 합치면 N - 1개의 그룹이 남고,

2번 합치면 N - 2개의 그룹이 남고,

N - K 번 합치면 K개의 그룹이 남는다

그래서 N - K번 합치기 위해서이다.

 

---

 

결론

그래서 1번 설명과 같이 diff를 구하고, 2번 설명과 같이 diff를 오름차순 정렬하여 [ 0 , N - K ) 범위로 더하게 되면 AC이다.

 

---

 

코드

package Greedy;
 
import java.util.*;
import java.io.*;
 
public class Main {
    static int atoi(String str){
        return Integer.parseInt(str);
    }
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        ArrayList<Integer> al = new ArrayList<>();
        ArrayList<Integer> diff = new ArrayList<>();
        int N = atoi(st.nextToken()); // 사람 인원 수
        int K = atoi(st.nextToken()); // 그룹 수
 
        st = new StringTokenizer(br.readLine());
 
        while(st.hasMoreTokens()){
            al.add(atoi(st.nextToken()));
        }
 
        for(int i = 0; i < al.size() - 1; i++){
            diff.add(al.get(i+1) - al.get(i)); //인접에 대한 차를 구함
        }
 
        Collections.sort(diff); // 오름차순
 
        int result = 0;
 
        for(int i = 0; i < N-K; i++){
            result += diff.get(i);
        }
 
        System.out.print(result);
    }
}