https://www.acmicpc.net/problem/25116
수영이가 쿠키런 맵을 만들고 싶고, 스테이지 난이도 수열이 주어진다.
● 한 맵에는 여러개의 스테이지가 있으며 연속적인 스테이지 난이도의 합이 M보다는 커야 한다.
● 난이도 합이 M보다는 커지는 연속적인 스테이지 구간이 K개 이상 존재해야 한다.
● 스테이지 난이도 수열의 난이도를 모두 X만큼 증가시킬 수 있다.
이때 스테이지 조건을 만족하는 가장 작은 X를 구하라는 문제다.
다음과 같은 문제는 X에 값을 대입해보면서 스테이지 조건을 만족하는 경우 중 최소값을 찾아야 한다.
이때 대입하는 방식이 이분탐색을 통해 정답 범위를 점점 좁혀가면서 X값을 찾아낼 수 있다.
따라서 작성해야할 코드는
1. 이분탐색 코드
2. 이분탐색 안에 스테이지 조건은 만족하는지에 대해 판별할 수 있는 로직이 필요하다.
한 맵에 연속적인 스테이지 난이도의 합이 M보다 크고 그 구간이 K개 이상 존재해야 한다는 조건은 웰노운인데 투 포인터로 구현할 수 있다.
코드는 다음과 같다.
#include <iostream>
#define lint long long
using namespace std;
lint n,m,k;
lint level[100001];
int main() {
cin >> n >> m >> k;
for(int i = 0; i < n; i++){
cin >> level[i];
}
lint left = 0, right = m, ans = -1;
while(left <= right){
lint mid = (left+right)/2;
lint cnt = 0, l = 0, r = 0, s = 0, v = 0;
while(l <= r && r < n){
if(l == r) {
s = level[l]+mid;
if(s >= m) {
cnt++;
}
r++;
s += (level[r]+mid);
continue;
}
if(s >= m) {
cnt += (n-r);
s -= (level[l]+mid);
l++;
}
else {
r++;
s += (level[r]+mid);
}
}
if(cnt >= k) {
right = mid - 1;
ans = mid;
}
else left = mid + 1;
}
cout << ans;
}
'📚알고리즘 > 백준' 카테고리의 다른 글
[백준 2048번] Hello, 2048! (0) | 2024.06.21 |
---|---|
[백준 12923번] 별 모으기 (C++) (1) | 2024.06.09 |
[백준 30805번] 사전 순 최대 공통 부분 수열 (C++) (0) | 2024.06.06 |
[백준 12020번] LU 분해 (C++) (0) | 2024.05.16 |
[백준 27977번] 킥보드로 등교하기 (C++) (0) | 2024.03.28 |