https://www.acmicpc.net/problem/17951
시험지의 개수와 시험지를 나눌 그룹의 수가 주어질 때, 시험지를 그룹으로 나눠 그룹들 중 총 점수의 최솟값을 구하는 문제다.
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
ex. 가능한 시간 복잡도, 알고리즘 선택
입출력 제한
- 1 ≤ K ≤ N ≤ 100,000
- 0 ≤ x ≤ 20
그룹으로 나눈 시험 점수의 최솟값을 매개 변수로 놓고 이분탐색 진행하면 100,000 × log (100,000)의 시간 안에 해결할 수 있다.
left는 입력받은 시험 점수 중 최솟값으로 두고, right는 시험 점수를 모두 더한 값으로 둔다. mid 값을 정하고 조건에 맞는 지 확인할 때, 그룹의 총 점수가 mid 값보다 크거나 같으면 그룹의 개수를 증가시키고 총 점수를 0으로 만든다. 이후, 반복문을 나오고 나서 남은 총 점수가 mid 값보다 크거나 같으면 그룹의 개수를 증가시켜야 한다.
코드 설계하기
위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!
- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지
- N, K 입력받기
- 각 시험지마다 맞은 문제의 개수 x 입력 받기
- 그룹으로 나눈 시험 점수의 최솟값을 매개 변수로 놓고 이분탐색 진행
- left = 0, right = 20 × N으로 놓고 조건에 맞는 지 확인해 mid 값을 갱신하며 진행
- 그룹으로 나눈 시험 점수의 최솟값 출력
시도 회차 수정 사항 (Optional)
- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!
1~2회차
- 정해놓은 최소 점수로 나눠진 그룹의 수가 k와 동일한 경우에만 ans 값을 갱신해야 함
- 그룹의 총 점수가 mid보다 크거나 같을 때 그룹의 개수를 증가시키고 총 점수를 0으로 초기화해야 함
정답 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,k,x,ans,all,mn=21;
vector<int> v;
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);
all += x;
mn = min(mn,x);
}
int l=mn,r=all;
while (l<=r) {
int mid = (l+r)/2,sum=0,cnt=0;
for (int i=0; i<n; i++) {
sum += v[i];
if (sum>=mid) {
cnt++;
sum = 0;
}
}
if (sum>=mid) {
cnt++;
}
if (cnt>=k) {
l=mid+1;
if (cnt==k)
ans = max(ans,mid);
}
else {
r=mid-1;
}
}
cout << ans;
}