[백준 25116번] TOO EASY Cookie Run (C++)

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;
}