Notice
Recent Posts
Recent Comments
Link
«   2025/03   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
Tags
more
Archives
Today
Total
관리 메뉴

끄적끄적

백준 [13164] 행복 유치원 본문

코테준비/백준

백준 [13164] 행복 유치원

alstj_성공 2022. 9. 2. 18:39

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

 

13164번: 행복 유치원

입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들

www.acmicpc.net

 

그리디

티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 구해야하는 문제이다.

우선 키 순서대로 줄을 세웠다고 했으므로 정렬을 해줌

그 다음 인접 원소간의 차이를 각각 구해주고, 이를 정렬해줌

K개의 조가 있다고 하면 K-1개의 경계가 있을 것인데

비용을 최소로 한다고 했기 때문에 차이가 큰 K-1개를 제외하고 더해주면 티셔츠 만드는 최소 비용을 구할 수 있다.

 

문제의 예제를 예로 들면 이런식

'코테준비 > 백준' 카테고리의 다른 글

백준 [1339] 단어 수학  (0) 2022.09.05
백준 [1931] 회의실 배정  (0) 2022.09.05
백준 [1052] 물병  (0) 2022.09.01
백준 [1715] 카드 정렬하기  (0) 2022.09.01
백준 [1759] 암호 만들기  (0) 2022.08.30