[Python] Baekjoon - 1449. 수리공 항승

백준 1449번 문제 수리공 항승은 직선 파이프에 N개의 구멍이 났을 때 테이프를 최소 몇 개 붙여 구멍을 모두 막을 수 있는지 구하는 문제다. 이 문제는 그리디 알고리즘과 정렬을 사용해 해결할 수 있다. 난이도는 실버 3이다. 

 

백준 1449번 수리공 항승 문제 정보

알고리즘 분류

- 그리디 알고리즘 및 정렬

난이도

- 실버 3

 

수리공 항승 문제 요약

직선 파이프에 N개의 구멍이 났을 때, 길이가 L인 테이프로 구멍을 막으려고 한다. 사용해야 하는 테이프의 최소 개수를 구하는 문제다.

 

문제 풀이 과정

왼쪽에서부터 테이프를 붙여가며 개수를 센다. 현재 상태에서 테이프를 붙여야 하는지 아닌지를 판단해서 붙이기 때문에 그리디 알고리즘이다.

 

코드

import sys


def get_min_tapes():
    global N, L, points

    cnt, now = 0, -1

    for point in points:
        if point > now:
            now = point + L -1
            cnt += 1

    return cnt


if __name__ == '__main__':
    N, L = map(int, input().split())
    points = sorted(list(map(int, sys.stdin.readline().split())))
    print(get_min_tapes())