[코딩테스트] - 행복 유치원 골드5 ( 백준(baekjoon) / java )👍

 

안녕하세요 나홀로전세집입니다.

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

 

13164번: 행복 유치원

 

 

오늘 풀어볼 문제는 백준 골드 문제 행복 유치원입니다.

행복 유치원

 

문제

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

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

입력

입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.

출력

티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.

 

원생들이 입을 셔츠의 최솟값의 합을 구하는 문제입니다.

 

 

 

int n = sc.nextInt(); // 원생의 수
int k = sc.nextInt(); // 조의 수
int[] height = new int[n]; // 원생의 키를 담는 배열
int[] gap = new int[n]; // 갭차이 배열
int count = 0; // 반복문에서 조의 수만큼 빼기 위한 변수
int sum = 0; // 출력 값

 

제가 선언한 변수는 다음과 같습니다.

 

원생과 나눌 조의 수를 각각 변수로 두고 키와 키의 차이를 다른 배열로 선언해서 초기화를 시켰습니다.

제가 고민해본 알고리즘은 갭 차이 배열에서 최댓값을 (조의 수 -1) 만큼 빼면 최솟값의 합이 되겠다고 생각했습니다.

 

 

제가 짠 코드를 보여드리겠습니다.

 

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 원생의 수
		int k = sc.nextInt(); // 조의 수
		int[] height = new int[n]; // 원생의 키를 담는 배열
		for (int i = 0; i < n; i++) { // 원생 초기화
			height[i] = sc.nextInt();
		}
		int[] gap = new int[n]; // 갭차이 배열
		for (int i = 0, j = 1; i < height.length; i++) {
			if (i < height.length - 1) {
				gap[i] = height[j] - height[i]; // 갭차이 초기화
				j++;
			}
		}
		
		Arrays.sort(gap); // 갭차이 배열 정렬
		
		int count = 0;
		
		for (int i = gap.length - 1; count < k - 1; i--) { // 갭 차이에서 최대값 들을 조 갯수 -1 만큼 빼면 최소갭의 합이 된다.
			gap[i] = 0; // 갭차이 최대값을 0으로 초기화
			count++; // 조만큼 빼기 위해 설정한 변수
		}
		int sum = 0;
		
		for (int i = 0; i < height.length; i++) {
			sum += gap[i]; // 최댓값을 뺀 갭차이를 더하면 최소갭차이가 된다.
		}
		
		System.out.println(sum);
	}

 

다음은 제가 짠 코드입니다. 

키 배열을 사용해 키 차이 배열을 만들어주었고, 이 배열을 정렬한 후 조만큼 최댓값을 0으로 변환시켜줬습니다.

최댓값을 뺀 키 차이를 더해주면 최소 키차이가 됩니다.

 

알고리즘을 고민하는데 꽤 오랜 시간이 걸렸습니다. 1시간 30분동안 풀었는데 앞으로 이런 문제들을 1시간 안에 푸는 것이 목표입니다.

 

 

 

 

 

 

전체코드

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 원생의 수
		int k = sc.nextInt(); // 조의 수
		int[] height = new int[n]; // 원생의 키를 담는 배열
		for (int i = 0; i < n; i++) { // 원생 초기화
			height[i] = sc.nextInt();
		}
		int[] gap = new int[n]; // 갭차이 배열
		for (int i = 0, j = 1; i < height.length; i++) {
			if (i < height.length - 1) {
				gap[i] = height[j] - height[i]; // 갭차이 초기화
				j++;
			}
		}
		
		Arrays.sort(gap); // 갭차이 배열 정렬
		
		int count = 0;
		
		for (int i = gap.length - 1; count < k - 1; i--) { // 갭 차이에서 최대값 들을 조 갯수 -1 만큼 빼면 최소갭의 합이 된다.
			gap[i] = 0; // 갭차이 최대값을 0으로 초기화
			count++; // 조만큼 빼기 위해 설정한 변수
		}
		int sum = 0;
		
		for (int i = 0; i < height.length; i++) {
			sum += gap[i]; // 최댓값을 뺀 갭차이를 더하면 최소갭차이가 된다.
		}
		
		System.out.println(sum);
	}
}

 

오늘도 즐코딩 하시고 좋은 하루 되세요~