https://www.acmicpc.net/problem/13164
N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 1명 있어야 하고 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원 수가 같을 필요는 없다. 나뉘어진 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 티셔츠를 만드는 비용이 생길 때, K개의 조에 대해 티셔츠를 만드는 비용의 합을 최소로 하는 문제다.
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
ex. 가능한 시간 복잡도, 알고리즘 선택
입출력 제한
- 1 ≤ N ≤ 300,000
- 1 ≤ K ≤ N
- 1 ≤ 원생의 키 ≤ 1,000,000,000
처음엔 N과 K가 너무 커서 O(nlogn) 안에 해결하기 위해 이분탐색으로 풀려고 했다. 그런데 코드를 쓰다 보니 원생의 키가 1,000,000,000까지 갈 수 있어서 mid 값을 구할 때 시간 초과가 날 것 같아 보였다.
키가 가장 큰 원생과 가장 작은 원생의 키 차이를 구할 때, 인접한 원생들의 키 차이를 모두 더하면 된다.
예를 들어 예제 입력처럼 1 3 5 6 10이 주어져 있을 때, 1인 원생과 10인 원생의 키 차이는 (3-1) + (5-3) + (6-5) + (10-6) = 9이다.
K개의 조로 나눌 때 원생들 사이에 K-1개의 막대기를 놓는다고 생각하면 원생들의 키 차이 중 값이 큰 곳에 막대기를 놓아야 키 차이를 최소로 만들 수 있다. 반복문을 돌면서 막대기를 놓은 곳 전까지 키 차이를 합해 티셔츠 비용을 구하고 모든 조의 티셔츠 비용을 더하면 문제의 답을 구할 수 있다.
코드 설계하기
위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!
- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지
- N, K,원생들의 키 입력받기
- 인접한 각 원생들의 키 차이를 기록하고, 가장 큰 순서대로 -1을 K-1개만큼 대입해 조를 나누기
- 각 조마다 -1이 나오기 전까지 키 차이 값을 모두 더해 티셔츠를 만드는 비용 구하기
- K개의 조에서 티셔츠를 만드는 최소 비용 출력하기
시도 회차 수정 사항 (Optional)
- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!
pass
정답 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,k,x,ans;
vector<int> v,hd;
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i=0; i<n; i++) {
cin >> x;
v.push_back(x);
}
for (int i=1; i<n; i++) hd.push_back(v[i]-v[i-1]);
sort(hd.begin(),hd.end());
for (int i=0; i<n-k; i++) ans+=hd[i];
cout << ans;
}