문제링크

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

 

사용 알고리즘

  º  이분탐색

 

시간복잡도

  º  $\mathcal{O}(Nlog(10000))$

 

풀이

 

N개의 수로 이루어진 배열에서 M개이하의 구간으로 나누어야 하는데, 구간을 나누어야 하는데 나눠진 구간은

구간내의 최댓값 최솟값의 차이를 구간의 점수로 사용합니다. 나누어진 구간들의 점수 중 최댓값을 가장 작게 구간을 나누는 문제입니다.

 

1) 임의의 구간의 점수의 최댓값을 지정하고

2) 그 점수가 사용 가능한지 검사하는 방법으로 해결했습니다.

 

1)은 입력 받은 수 중의 최대값을 right값 최소값인 0을 left값으로 하여 이분탐색을 진행합니다.

$\mathcal{O}(log(10000))$=4의 시간소모. 10000은 입력으로 받을 수 있는 값의 최댓값.

 

2)은 별도의 함수를 만들어 주는데 함수의 로직은 다음과 같습니다.

  (1) n개의 숫자를 for문으로 탐색하며 매 index에서 최솟값과 최댓값을 계속 갱신해줍니다.

  (2) 그 후 현 위치의 (최댓값-최솟값)≤검사할 구간의 점수 가 성립하는지 검사를 합니다.

     if 성립하지 않다면 구간의 개수를 하나 추가 그리고 현재 index의 수를 최솟값 최댓값으로 만들어주고 다음 indxe의 검사를 해줍니다.

  (3) 검사해서 나온 구간의 개수가 m보다 작거나 같다면 검사결과를 true, 아니라면 false로 출력해줍니다.

$\mathcal{O}(log(N)$의 시간소모.

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector <int> v;
bool check(int mid)
{
    int max_num=-1,min_num=10001, cnt = 1;
    for (int i = 0; i < n; i++)
    {
        if (i == 0)
        {
            min_num = v[i];
            max_num = v[i];
        }
        if (v[i] < min_num) // 최솟값 갱신
            min_num = v[i];
        if (v[i] > max_num) // 최댓값 갱신
            max_num = v[i];
        if (max_num - min_num > mid) // 구간의 점수가 넘어가면
        {
            cnt += 1// 새로운 구간 시작
            max_num = v[i];
            min_num = v[i];
        }
    }
    if (m >= cnt)
        return true;
    else
        return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m;
    v.resize(n);
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        sum += v[i];
    }
    int ans=1987654321,mid, left = 0, right = sum;
    while (left <= right) // // 구간의 점수값 이분탐색
    {
        mid = (left + right) / 2
        if (check(mid))
        {
            right = mid - 1;
            if (mid < ans)
                ans = mid;
        }
        else
            left = mid + 1;
    }
    cout << ans;
    return 0;
}
Colored by Color Scripter
cs

'Algorithm > boj' 카테고리의 다른 글

백준 1654번 랜선 자르기  (0) 2021.10.24
백준 11651번 좌표 정렬하기 2  (0) 2021.10.24
백준 1939번 중량제한  (0) 2021.10.24
백준 2805번 나무 자르기  (0) 2021.10.24
백준 2110번 공유기 설치  (1) 2021.10.24

+ Recent posts