쉬운듯 아닌듯 내 기준에 굉장히 까다로웠던 문제라서 기록하려 한다.
✍ 문제 설명
📝 문제 풀이
처음 접했을 때는 최댓값이 최소가 되도록 그룹을 묶는 방법이 생각이 안났다.
'주어진 그룹 수(M)로 나눠볼까?' 라는 생각도 잠시, 나눠지기만 할뿐 최소합을 찾기란 쉽지 않았다.
그러다 밑에 있는 알고리즘 힌트를 봤는데, 엥? 이분 탐색이 있는 것이었다.
정렬 할 수 있는 문제도 아니고, 주어진 수의 범위가 적은데도 불구하고 말이다.
다시 오랜 시간 생각하니,
이분 탐색으로 구슬 묶음(mid와 구슬의 합을 비교하여 묶음) 마다 count를 하여 구슬 묶음과 비교하면 되겠다는 생각이 났다.
- 만약 count가 구슬 묶음(M)보다 클 경우는 측정한 타겟 값이 정답 값보다 작은 것이므로
if(count > M) lower = mid + 1; // 최소치를 올려 다시 최댓값 측정 - 반대의 경우에는 측정한 타겟 값이 정답 값보다 큰 것이므로
(M과 count의 값이 같더라도 그 중에서 최소를 찾아야되기 때문에 최대치를 내려 재탐색한다)if(count <= M) upper = mid - 1; // 최대치를 내려 다시 최댓값 측정
이런 식으로 탐색이 완료되면 결국 구슬 묶음(M) 만큼의 최솟값이 나오게 된다.
(찾아보니 이렇게 이분 탐색으로 주어진 범위에서 최적해를 찾는 것을 Parametric Search라 한다고 한다)
이렇게 한 고비가 넘어가고 두 번째 고비가 찾아왔다 ㅋㅋ.
사실 이분 탐색으로 최적해를 찾는 것이 이 문제의 핵심이지만.. 나의 모자람이.. 부족한 꼼꼼함이.. 문제를 푸는 데에 있어 파국으로 가져왔다.
묶은 구슬이 어떻게 묶였는지 여부도 출력해야 하는데, 반례를 너무 가볍게 생각한 나머지 올바르게 출력시키는데도 꽤 많은 시간이 소요됐다.. (도저히 반례를 모르겠어서 다른 분들의 코드를 참조했다)
그리고 결국 해냈다.
✅ 정답 코드
import java.util.*;
import java.io.*;
public class Main {
static int[] beads;
static int N, M;
static int lower = 0, upper = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 구슬 수
M = Integer.parseInt(st.nextToken()); // 묶음 수
beads = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
beads[i] = Integer.parseInt(st.nextToken());
lower = Math.max(lower, beads[i]); // 구슬 합의 최소 범위
upper += beads[i]; // 구슬 합의 최대 범위
}
binarySearch(); // 이분 탐색으로 값 찾기
System.out.println(lower); // 구슬 합의 최댓값 출력
StringBuilder sb = new StringBuilder();
int cnt = 0;
int sum = 0;
for (int i = 0; i < N; i++) {
sum += beads[i];
if (sum > lower) { // 만약 구슬 합이 최댓값보다 크면
M--; // 묶음이 하나 만들어진 것이므로 M--;
sum = beads[i];
sb.append(cnt).append(" "); // 현재 구슬 수를 sb에 추가
cnt = 1; // 다시 구슬 수를 1로 카운트
} else {
cnt++;
}
if(M == N - i) break; // 묶음 수가 1인 경우를 세어 주기 위해
}
// 현재 M == (남은 묶음 수) 이므로
// 구슬이 다 묶일 때까지 M--;
while(M-- > 0) {
// 위에 for문에서 최댓값에 도달하지 못한 합의 구슬 수를 먼저 추가
sb.append(cnt).append(" ");
// 그 다음은 다 1씩 묶음이므로
cnt = 1;
}
System.out.println(sb);
}
static void binarySearch() {
int mid = 0;
while (upper >= lower) {
// 1. 범위 내의 mid값을 특정(구슬 합의 최댓값)
mid = (upper + lower) / 2;
// 3. mid 값에 대한 구슬 묶음 수
int cnt = cntBeadsBundle(mid);
// 4. 묶음 수(cnt)와 묶여야할 수(M)를 비교
if (cnt > M) {
lower = mid + 1;
} else {
upper = mid - 1;
}
}
}
static int cntBeadsBundle(int mid) {
int sum = 0;
int cnt = 1;
// 2. 범위 내의 중간 값(mid)과 구슬 합을 비교하여 cnt를 센다
for (int i = 0; i < N; i++) {
sum += beads[i];
if (sum > mid) {
cnt++;
sum = beads[i];
}
}
return cnt;
}
}🎈 후기
이분 탐색에 대한 고정관념(방대한 수의 탐색만을 위해 써야징)이 있으면 접근조차 너무 어려웠던 문제였다. 이 문제를 시작으로 Parametric Search에 대해 좀 더 알아봐야겠다.
푸는 데에 너무 오래 걸린 감이 있지만, 그래도 해냈다는데에 의의를 둬야겠다.😆
Parametric Search 관련글 <- 문제 푸는 데에 도움이 많이 됐다!
