[백준 17179번 C/C++] 케이크 자르기
[백준 17179번 C/C++] 케이크 자르기
https://www.acmicpc.net/problem/17179
해결전략
이분탐색, 매개변수 탐색
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// n: 자르는 횟수, m: 자를 수 있는 위치 개수, l: 롤 케이크의 길이를 저장
int n, m, l;
// v: 자르는 위치를 저장할 벡터
vector<int> v;
// 목표한 크기의 조각으로 롤 케이크를 자를 수 있는지 판별
bool isValid(int givenCnt, int piecelength)
{
int cnt = 0; // 롤 케이크를 자른 횟수
int cuttingLocation = 0; // 자른 롤 케이크의 위치
// 자를 수 있는 위치를 순회하면서, 목표 횟수에 도달할 때까지 자른다
for(int i = 0; i < m && cnt < givenCnt; i++)
{
if (v[i] - cuttingLocation >= piecelength)
{
cnt++;
cuttingLocation = v[i];
}
}
// 목표 횟수로 자르고 남은 롤 케이크도 목표하는 크기이면 true를 반환
if (cnt == givenCnt && l - cuttingLocation >= piecelength)
return true;
return false;
}
int Cut(int givenCnt, int length)
{
//이분탐색 초기값
int left = 1; // 최소 케이크 조각 길이
int right = length; // 최대 케이크 조각 길이
int result = 0; // givenCnt 회 자른 경우 가장 작은 조각 길이의 최댓값
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if(isValid(givenCnt, mid))
{
result = mid; // 가장 작은 조각의 최대 길이를 업데이트
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m >> l;
v.resize(m);
for(int i = 0; i < m; i++){
cin >> v[i];
}
// 자르는 위치를 정렬. 해당문제는 굳이 정렬하지 않아도 된다.
sort(v.begin(), v.end());
for(int i = 0; i < n; i++){
int givenCnt;
cin >> givenCnt;
cout << Cut(givenCnt, l) << "\n";
}
return 0;
}
'⭐ 코딩테스트 > 백준' 카테고리의 다른 글
[백준 1012번 C/C++] 유기농 배추 (0) | 2023.08.18 |
---|---|
[백준 11660번 C/C++] 구간 합 구하기 5 (0) | 2023.08.16 |
[백준 26069번 C/C++] 붙임성 좋은 총총이 (0) | 2023.08.10 |
[백준 2178번 C/C++] 미로 탐색 (0) | 2023.08.09 |
[백준 16493번 C/C++] 최대 페이지 수 (0) | 2023.08.08 |
댓글
이 글 공유하기
다른 글
-
[백준 1012번 C/C++] 유기농 배추
[백준 1012번 C/C++] 유기농 배추
2023.08.18 -
[백준 11660번 C/C++] 구간 합 구하기 5
[백준 11660번 C/C++] 구간 합 구하기 5
2023.08.16 -
[백준 26069번 C/C++] 붙임성 좋은 총총이
[백준 26069번 C/C++] 붙임성 좋은 총총이
2023.08.10 -
[백준 2178번 C/C++] 미로 탐색
[백준 2178번 C/C++] 미로 탐색
2023.08.09