BOJ 1449 수리공 항승

문제

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

이 문제 자체보다 다음의 변형된 문제에 주목하자.

회의실 배정 문제처럼 N개의 구간들이 주어질 때 이 구간들을 최소한으로 선택해 그 합집합이 전체 구간을 모두 덮을 수 있도록 해야 한다.

 

풀이

가장 왼쪽 점을 지나는 구간들 중 가장 오른쪽으로 멀리 뻗어 나가는 구간을 선택한다.

 

<Greedy Choice Property>

그리디 알고리즘이 아닌 다른 최적해의 구간 M1, M2, ... 이 있다고 가정하자.

이때 가장 왼쪽 점을 포함하는 구간들 중 제일 오른쪽으로 멀리 뻗어 나가는 구간은 S라 하자.

M1과 S는 모두 제일 왼쪽 점을 포함하지만, S는 더 멀리 나가니, M1을 S로 바꿔도 최적해가 된다.

 

<Optimal Substructure>

자명하다.

 

시간 복잡도 : $O(N)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1000;

int n, l;
int arr[MAXN+10];
int ans;

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;

    scanf("%d%d", &n, &l); l--;
    for(i=0; i<n; i++) scanf("%d", &arr[i]);

    sort(arr, arr+n);

    for(i=0; i<n; )
    {
        int now = arr[i];
        for(; arr[i]<=now+l && i<n; i++);
        ans++;
    }
    printf("%d", ans);
}