[백준] 13397번 구간 나누기 2 (Gold 4)

 

 

문제 링크 : https://www.acmicpc.net/problem/13397

 

1. 문제 접근

• N개의 수로 이루어진 배열을 m개의 구간으로 나누어야 한다.
• 하나의 구간은 하나 이상의 연속된 수로 이루어져 있다.
• 구간의 점수 = 구간 내 최대값 - 구간 내 최소값
• "n개의 수로 이루어진 배열" 과 "구간의 개수 m"이 주어졌을 때, "구간의 점수"의 최댓값의 최소값을 구하는 문제

일단 이 문제를 이해하기 전 최대값의 최소값이 무엇인지 알아보자.

정말 말도 안되는 말인 것 같지만 문장의 흐름을 어느 구간에서 끊는가가 문제를 이해하는데 아주 큰 도움이 된다.

구간의 점수의 최댓값 / 의 최소값 이라고 생각해보자.

• m개의 구간에서 "구간의 점수"가 나올 것이다.
• 이러한 각 구간의 점수의 최대값을 구해보자.
  • 만약 제시된 예제와 같이 배열이 [1, 5, 4, 6, 2, 1, 3, 7]이 주어진다고 생각해보자.
  • 구간을 [1, 5] / [4, 6, 2] / [1, 3, 7] 로 나눈다면 각 구간의 점수는 4, 4, 6점이 나오고 최대값은 6점이다.
  • 그렇다면 구간을 [1, 5, 4] / [6, 2, 1] / [3, 7] 로 나눈다면 각 구간의 점수는 4, 5, 4점이 나오고 최대값은 5점이다.
  • 이렇게 구간을 계속해서 나눴을 때의 최대값 중 가장 작은 값은 바로 위에 나온 5점이 최소값이 된다.

 

문제와 별개로 보통 "최대값의 최소값" or "최소값의 최대값" 과 같은 이해하기 어려운 말이 나올때가 있다.

이때, 당황하지 말고 일단 문제의 갈피를 이분탐색 중 "매개변수 탐색" 알고리즘을 사용하면 된다.

문제를 쉽게 이해하면 "oooooooxxxxx" 배열에서 가장 오른쪽에 있는 o를 찾는다 생각해보자. 

매개변수 탐색은 해당 포스팅을 확인해보자

 

이진 탐색 / 매개 변수 탐색

 

 

2. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
using namespace std;

#define MAX 10000
#define INF 987654321

int n, m;
vector<int> v;
int answer = INF;
bool solve(int num)
{
    int res = 1;
    int mx = v[0], mn = v[0];
    for (int i = 0; i < v.size(); i++)
    {
        mx = max(mx, v[i]);
        mn = min(mn, v[i]);

        if (mx - mn > num)
        {
            res++;
            mx = v[i];
            mn = v[i];
        }
    }
    return res <= m;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        v.push_back(x);
    }
    int l = 0;
    int r = *max_element(v.begin(), v.end()) - *min_element(v.begin(), v.end());

    answer = r;

    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (solve(mid))
        {
            answer = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << answer << endl;
    return 0;
}

 

추가로 *max_element에서 *를 반드시 써줘야한다.!!!