K개의 자를 수 있는 위치가 정해져있는 L길이의 통나무가 있다.
C번 통나무를 잘라서 가장 긴 조각이 최소가 되도록 하는 조각의 길이와 처음 자르는 위치를 구하는
문제다.
문제를 보고 DP아니면 이분탐색일 것이라고 생각 되었다.
DP로 풀기에는 K와 C가 조금 크고 점화식도 까다롭게 생각될거 같아 이분탐색으로 풀이를
만들었는데 성립되었다.
잘라진 조각을 이분탐색 하여 그 조각이 성립되는지 greedy하게 $O(K*logL)$만에 찾을 수 있다.
나름 내 방식대로 짜다가 60%에서 틀려서 다른 분의 코드를 참고했다.
이런문제는 풀이법을 알아도 정확한 조건을 주지 않으면 정답이 나오지 않는다.
조건을 간략히, 명백하게 만들어야한다.
이분탐색에서 가능한지 확인하는 함수 isPossible()은 다음과 같은 과정을 거친다.
1. 한단계씩 넓혀가면서 차이값을 누적한다.
2. 누적 값이 원하는 조각보다 클 경우 cut를 해야한다.
3. 누적 값을 한단계 차이값으로 초기화 하는데 이 값도 원하는 조각보다 큰 경우는
성립되지 않는 경우다.
4. cut수가 C보다 작거나 같으면 성립된다.
#include <cstdio>
#include <algorithm>
using namespace std;
int L, K, C;
int cut[10002];
bool isPossible(int log) {
int k;
int start = L, cnt = 0;
int diff = 0;
for (k = K - 1;k >= 0;k--) {
diff += cut[k + 1] - cut[k];
if (diff > log) {
diff = cut[k+1]-cut[k];
cnt++;
if (diff > log) {
cnt = C + 1;
break;
}
}
}
return cnt <= C;
}
bool isFirst(int idx, int log) {
int k;
int start = cut[idx], cnt = 1;
if (cut[idx] - start > log) return false;
if (cnt == C) {
if (L - cut[idx] <= log) return true;
else return false;
}
int diff = 0;
for (k = idx + 1;k <= K;k++) {
diff += cut[k + 1] - cut[k];
if (diff > log) {
diff = cut[k + 1] - cut[k];
cnt++;
if (diff > log) {
cnt = C + 1;
break;
}
}
}
return cnt <= C;
}
int main() {
scanf("%d%d%d", &L, &K, &C);
for (int k = 1;k <= K;k++) scanf("%d", &cut[k]);
cut[0] = 0, cut[++K] = L;
sort(cut, cut + K + 1);
int ans1 = (int)2e9;
int l = 0, r = (int)(1e9 + 1);
while (l <= r) {
int mid = (l + r) / 2;
if (isPossible(mid)) {
ans1 = min(ans1, mid);
r = mid - 1;
}
else l = mid + 1;
}
int diff = 0, cnt = 0;
int idx = K;
for (int k = K - 1;k >= 0;k--) {
diff += cut[k + 1] - cut[k];
if (diff > ans1) {
cnt++;
diff = cut[k + 1] - cut[k];
idx = k + 1;
}
}
if (cnt < C) idx = 1;
printf("%d %d\n", ans1, cut[idx]);
return 0;
}
| cs |
저 문제 구현하는 데 약간 헤멘 기억이 나네요..
답글삭제이런 문제가 구현하기가 힘들어용ㅠㅠ
삭제