13164번: 행복 유치원
행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로
www.acmicpc.net
> 의식의 흐름
dfs를 써서 모든 경우에 대해 비용을 구하고 그 중 최소를 뽑으면 되지 않을까? => 시간초과
옆 사람과의 키 차이가 얼마인지 구한 뒤에 차이가 큰 부분을 잘라서 조로 나눠버리면 될 것 같은데..? => 성공
> 풀이 과정
1. 원생의 수(N), 조의 개수(K)를 입력 받는다.
2. 모든 원생의 키를 배열(heights)에 저장한다.
3. 옆 원생과의 키 차이를 배열(gap)에 저장한다.
4. 배열 gap을 오름차순으로 정렬한 후 `N-K`개의 합을 구한다.
# 비용 구하는 방법
5명을 3개 조로 나누는 경우 : (5-3)개의 키 차이 합을 구해야 함.
5명을 1개 조로 나누는 경우 : (5-1)개의 키 차이 합을 구해야 함.
=> N명을 K개 조로 나누는 경우 : (N-K)개의 키 차이 합을 구해야 함.
5. 4번에서 구한 값을 출력한다.
> 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int N, K;
public static int[] heights;
public static int[] gap;
public static int ans = 0;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 원생의 수
K = Integer.parseInt(st.nextToken()); // 조의 개수
heights = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++){
heights[i] = Integer.parseInt(st.nextToken());
}
gap = new int[N-1];
for(int i=1;i<N;i++){
gap[i-1] = heights[i] - heights[i-1];
}
Arrays.sort(gap); // 오름차순 정렬
for(int i=0;i<N-K;i++){
ans += gap[i];
}
bw.write(Integer.toString(ans));
bw.flush();
br.close();
bw.close();
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[JAVA] 백준 q11053 - 가장 긴 증가하는 부분 수열 (2) | 2023.10.16 |
---|---|
[JAVA] 백준 q2212 - 센서 (0) | 2023.10.13 |
[JAVA] 백준 q1541 - 잃어버린 괄호 (2) | 2023.10.10 |
[JAVA] 백준 q5639 - 이진 검색 트리 (0) | 2023.10.04 |
[JAVA] 백준 q1991 - 트리 순회 (0) | 2023.09.21 |