끄적끄적
백준 [13164] 행복 유치원 본문
출처 : 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 |