https://www.acmicpc.net/problem/17179
문제 해결 과정
착안
자르고자 하는 케이크 조각 수를 만족하기 위해 자연수 1부터 $L$까지의 길이 중 가능한 길이의 최댓값을 이진 탐색(binary search, 이분 탐색)을 응용하여 구한다.
구현
편의상 시작 탐색 구간의 우측 끝값을 불가능한 길이인 $L+1$로 설정하여 탐색을 시작하고 아래 코드와 같이 탐색 알고리즘을 구현하였다.
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
#include <iostream>
using namespace std;
int Points[1002];
int N, M, L;
bool Cuttable(int len, int count)
{
int cnt = 0;
int start = 0;
for (int i = 0; i <= M + 1; i++)
{
if (Points[i] - Points[start] >= len)
{
cnt++;
start = i;
}
}
return cnt >= count;
}
int BinarySearch(int left, int right, int count)
{
while (left < right)
{
int len = (left + right) / 2;
if (Cuttable(len, count))
left = len + 1;
else
right = len;
}
return right - 1;
}
int main()
{
cin >> N >> M >> L;
Points[M + 1] = L;
for (int i = 1; i <= M; i++)
cin >> Points[i];
while (N--)
{
int CutCount;
cin >> CutCount;
cout << BinarySearch(1, L + 1, CutCount + 1) << "\n";
}
return 0;
}
실행 결과
'C++ 코딩 문제 풀이 > 백준' 카테고리의 다른 글
[Baekjoon] 11660번: 구간 합 구하기 5 (0) | 2023.08.24 |
---|---|
[Baekjoon] 14502번: 연구소 (0) | 2023.08.15 |
[Baekjoon] 16493번: 최대 페이지 수 (0) | 2023.08.08 |
[Baekjoon] 12865번: 평범한 배낭 (0) | 2023.08.01 |
[Baekjoon] 1629번: 곱셈 (0) | 2023.07.31 |
댓글