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

https://www.acmicpc.net/problem/25116

Cookie Run 게임은 N개의 스테이지로 이루어진 맵을 달리는 게임이다. 맵을 디자인하는 데엔 아래와 같은 규칙이 있다.

1. 각 스테이지는 A0, A1, ..., A(N-1)의 난이도가 주어진다.
2. 연속적인 스테이지의 난이도 합이 M보다 크거나 같다면, 그 구역을 interesting section으로 부른다.
   1. Ai + ... + Aj ≥ M  & 0 ≤ i ≤ j ≤ N-1, section (i, j) = interesting section
3. 맵에는 적어도 K개의 interesting section이 있어야 한다.

 

게임이 너무 쉽다는 문제를 해결하기 위해 모든 스테이지의 난이도를 X만큼 올릴 수 있다고 할 때, 위의 조건을 만족하는 음이 아닌 정수 X의 최솟값을 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 1,000,000,000,000,000,000
• 1 ≤ K ≤ N(N+1)/2
• 0 ≤ Ai ≤ 1,000,000,000 (0 ≤ i ≤ N-1)

 

M의 값이 int 범위를 넘기 때문에 모든 변수는 long long int로 선언해두는 게 좋다.

 

추가 난이도 X를 매개변수로 선택하고 이분탐색을 진행한다. 합이 M 이상인 구간의 개수를 세고, 개수가 K보다 크거나 같다면 X의 최솟값인 mn을 갱신하면서 r을 줄인다. K보다 작다면 l을 높여야 한다.

 

합이 M 이상인 구간의 개수를 셀 때, N이 100,000이므로 이중 반복문을 돌릴 수 없기 때문에 누적 합과 투 포인터를 사용해야 한다. 이분탐색과 투 포인터의 변수를 헷갈리지 않게 선언하고, left와 right 모두 0으로 놓고 오른쪽으로 진행한다. 이때, 구간의 합이 M 이상일 경우, 그 뒤에 뭘 추가하든 M을 이미 넘겼으므로 cnt에 n에서 right를 빼고 1을 더한 값을 추가해야 한다.

 

누적 합 + 투 포인터는 1806 - 부분합 문제를 참고하면 좋다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, M, K, 난이도 정보 입력받기
2. 추가 난이도 X를 매개변수로 놓고 이분탐색 진행
   1. 누적 합과 투 포인터를 통해 합이 M 이상인 구간의 개수 세기
   2. 개수가 K 이상이라면 r을 줄이고 mn 갱신하기
   3. 개수가 K 미만이라면 l을 높이기
3. mn 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

1~4회차

• 변수들이 int 범위를 넘기 때문에 long long int로 선언해야 함
• 이분탐색 시 r의 초기값은 m으로 설정해야 함 (r ≤ 100이라는 조건은 서브 태스크)

 

---

정답 코드

#include <iostream>
using namespace std;

long long int n,m,k,arr[100001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(); cout.tie();

    cin >> n >> m >> k;
    for (int i=0; i<n; i++) cin >> arr[i];

    long long int l=0,r=m,mn=m+1;
    while (l<=r) {
        long long int mid=(l+r)/2,sum=0,cnt=0,left=0,right=0;

        while (left<=right) {
            if (sum>=m) {
                sum -= arr[left++] + mid;
                cnt += n-right+1;
            }
            else if (right==n) break;
            else sum += arr[right++] + mid;
        }

        if (cnt>=k) {
            r = mid-1;
            mn = min(mn,mid);
        }
        else {
            l = mid+1;
        }
    }

    cout << mn;
}