[백준] 13397 - 구간 나누기2 (C++)

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

N개의 수로 이뤄진 1차원 배열이 있고, 이 배열을 M개 이하의 구간으로 나눠 구간의 점수의 최댓값을 최소로 하려고 한다. 구간은 다음과 같은 조건을 만족해야 한다.

1. 하나의 구간은 하나 이상의 연속된 수들로 이루어짐
2. 배열의 각 수는 모두 하나의 구간에 포함돼야 함
3. 구간의 점수 = 구간에 속한 수의 최댓값 - 최솟값

배열과 M이 주어질 때, (구간의 점수의 최댓값)의 최솟값을 구하는 문제다.

 

---

문제 탐색하기

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

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

입출력 제한

• 1  ≤ N ≤ 5,000
• 1 ≤ M ≤ N
• 1 ≤ 배열에 들어있는 수 ≤ 10,000

 

구간의 점수의 최댓값을 매개 변수로 놓고 이분탐색을 진행한다. left = 0, right = (배열의 최댓값)으로 놓고 구한 mid를 넘지 않는 구간의 개수를 세고 개수에 따라 left 또는 right 값을 갱신한다.

 

---

코드 설계하기

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

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

1. N, M, 배열 입력받기
2. 구간의 점수의 최댓값을 매개 변수로 놓고 이분탐색을 진행
   1. 구한 구간의 점수의 최댓값을 기준으로 구간의 개수를 구하기
      1. 개수가 m보다 크면 l 갱신
      2. 개수가 m보다 작거나 같으면 r 갱신 & 구간의 점수의 최댓값의 최솟값 갱신
3. 구간의 점수의 최댓값의 최솟값 출력

 

---

시도 회차 수정 사항 (Optional)

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

pass

 

---

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n,m,x[5001],mx_x,ans=1e9;

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

    cin >> n >> m;
    for (int i=0; i<n; i++) {
        cin >> x[i];
        mx_x = max(mx_x,x[i]);
    }

    int l=0, r=mx_x;
    while (l<=r) {
        int mid = (l+r)/2,mn=mx_x,mx=0,cnt=1;

        for (int i=0; i<n; i++) {
            mn = min(mn,x[i]);
            mx = max(mx,x[i]);

            if (mx-mn>mid) {
                cnt++;
                mn = mx_x;
                mx = 0;
                i--;
            }
        }

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

    cout << ans;
}