백준 #1449 수리공 항승


BOJ #1449 - 수리공 항승

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

# 문제 분류

그리디 알고리즘

풀이 접근 방법


  1. 입력들은 파이프에서 물이 새는 위치이므로, 그리디 알고리즘을 사용하기 위해 정렬해준다.
  2. 물이 새는 위치를 발견하면 테이프의 시작점을 붙인다고 생각하고 tmp 값에 저장해준다.
  3. 다음 입력이 tmp + L - 1 범주 안에 들어오면 테이프의 범위 안에 있으므로 무시, 아니라면 tmp를 갱신하고 답에 1을 추가!

별 특별한 것 없는 강의실 배정 급의 그리디 알고리즘 문제다.
그리디 알고리즘을 처음 익힐 때 풀어보면 알고리즘을 이해하기 쉬울.. 정도..?
답을 나타내는 변수 이름으로는 cnt를 사용했다.

소스 코드


#include <iostream>
#include <algorithm>

using namespace std;

int N, L, k, tmp, cnt;
int arr[1010];

int main(){
    cin >> N >> L;

    for(int i=0; i<N; i++){
        cin >> arr[i];
    }

    sort(arr, arr+N);

    for(int i=0; i<N; i++){
        if(tmp == 0){
            tmp = arr[i];
            cnt++;
        }
        else{
            if(tmp + L - 1 >= arr[i]);
            else{
                tmp = arr[i];
                cnt++;
            }
        }
    }

    cout << cnt << endl;

    return 0;
}