백준 13164번: 행복 유치원 (Python/Java)

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

13164번: 행복 유치원

 

 

 

접근

---

우선 근처에 있는 원생들의 키 차이를 알아야 한다. 그래야 어떻게 원생 그룹을 나눴을 때, 가장 많은 차이가 나는지 알 수 있기 때문이다. 바로 옆 원생들끼리의 차이를 구해 따로 리스트를 만든다. 이제 해당 리스트들을 오름차순으로 정렬한다. 이때 이 정렬을 기준으로 원생들의 키를 나눌 수 있다. 가장 차이가 많이 나는 원생들을 기준으로 나누는 건 피하고 나머지 원생들을 기준으로 더해준다. 즉, 정렬된 리스트들을 앞에서부터 더해주면 가장 작은 차이의 그룹 합을 구할 수 있다.

 

 

 

풀이

---

Python

kidsNum, groupNum = map(int, (input()).split())
heightList = list(map(int, (input()).split()))

diffList = []
for i in range(1, kidsNum):
    diffList.append(heightList[i]-heightList[i-1])
diffList.sort()

result = 0
for i in range(kidsNum-groupNum):
    result += diffList[i]

print(result)

 

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        String[] firstLine = (scan.nextLine()).split(" ");
        int kidsNum = Integer.parseInt(firstLine[0]), groupNum = Integer.parseInt(firstLine[1]);

        String[] secondLine = (scan.nextLine()).split(" ");
        int[] heightList = new int[kidsNum];
        for(int i = 0 ; i < kidsNum ; i++){
            heightList[i] = Integer.parseInt(secondLine[i]);
        }

        int[] diffList = new int[kidsNum-1];
        for(int i = 1 ; i < kidsNum ; i++){
            diffList[i-1] = (heightList[i]-heightList[i-1]);
        }
        Arrays.sort(diffList);

        int result = 0;
        for(int i = 0 ; i < (kidsNum-groupNum) ; i++){
            result += diffList[i];
        }

        System.out.println(result);

    }

}

 

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        String[] firstLine = (scan.nextLine()).split(" ");
        int kidsNum = Integer.parseInt(firstLine[0]), groupNum = Integer.parseInt(firstLine[1]);

        String[] secondLine = (scan.nextLine()).split(" ");
        int[] heightList = new int[kidsNum];
        for(int i = 0 ; i < kidsNum ; i++){
            heightList[i] = Integer.parseInt(secondLine[i]);
        }

        int[] diffList = new int[kidsNum-1];
        for(int i = 1 ; i < kidsNum ; i++){
            diffList[i-1] = (heightList[i]-heightList[i-1]);
        }
        Arrays.sort(diffList);

        int result = 0;
        for(int i = 0 ; i < (kidsNum-groupNum) ; i++){
            result += diffList[i];
        }

        System.out.println(result);

    }

}

 

후기

---

개인적인 일정으로 인해 문제를 풀 시간이 없어 엄청 대충 풀었던 문제다. 다시 생각해보니 풀이도 헷갈리고 나 스스로도 문제를 통해 얻을 수 있는 지식들이 제대로 체득되지 않은 것이 느껴졌다. 알고리즘을 풀 때, 이렇게 급하게 풀면 스스로도 이게 제대로 풀린 건지 모르고 허겁지겁 풀 때가 있다. 사실 그렇게 푸는 게 무슨 의미가 있냐는 생각이 들고, 1일 1 알고리즘의 의미가 퇴색되는 기분이다. 그렇게 풀 바엔 그냥 볼일 다 보고 나중에 푸는 게 나을 수도 있다고 생각하기도 하고. 앞으로는 주의해서 미리 집중해서 풀어두거나, 아예 제대로 풀거나 해야겠다.