[백준] 13164 - 행복 유치원 (JAVA)

1. 소요시간 : 10분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 5
4. 문제 유형 : 그리디 알고리즘, 정렬
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : O
7. 문제 링크 : https://www.acmicpc.net/problem/13164
8. 푼 날짜 : 2023.04.03

1. 사용한 자료구조 & 알고리즘

그리디 알고리즘, 정렬을 사용했다.

2. 풀이과정

1. 값이 이미 정렬된 형태로 주어지므로 불필요하게 1번 더 정렬하지 않은 채로 arr배열에 담는다.
2. 이제 각각 값들의 차이를 저장한다.
3. 각각 값들의 차는 정렬한다.
4. N-K 번만큼 정렬된 배열의 값들을 가장 낮은 값부터 순서대로 더해준다.

-> 예를 들어 예제 입력으로 보면 각각
값들은 1,3,5,6,10
각각 값들의 차는 2,2,1,4
정렬하면 1,2,2,4
N-K는 5-3 = 2.
가장 낮은 값부터 차례대로 2번 더해주면 1+2 = 3

3. 소스코드

import java.util.*;
import java.io.*;


public class Main {
	
	public static void main(String[] args) throws IOException {

		BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;
		
		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int K=Integer.parseInt(st.nextToken());
		
		st=new StringTokenizer(br.readLine());
		int arr[]=new int[N];
		for(int i=0;i<arr.length;i++)
			arr[i]=Integer.parseInt(st.nextToken());
		
		int diff[]=new int[arr.length-1];
		for(int i=0;i<diff.length;i++) {
			diff[i]=arr[i+1]-arr[i];
		}
		Arrays.sort(diff);
		int sum=0;
		for(int i=0;i<N-K;i++) {
			sum+=diff[i];
		}
		System.out.println(sum);
		
	}
}

4. 결과

1달 전에 풀려다가 못풀어서 다른 사람 풀이보고 풀었었는데
오늘 다시 풀었을 때는 금방 풀었다 !

5. 회고

내가 더 잘해진 걸까
문제 유형을 기억하고 있어서 금방 푼 걸까

문제가 쉬워 보인다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212