BOJ 1449 - 수리공 항승

문제

백준 온라인 저지 - 1449번

풀이 과정

테이프를 겹치는 것이 가능하므로 탐욕 알고리즘 을 사용해서 최소 테이프 개수를 구할 수 있습니다.

항상 최대 길이의 테이프를 사용하기 때문에 물이 새는 구간을 오름차순 정렬하면 맨 앞부터 테이프를 붙이면 되는 것입니다.
이때 문제 조건에 입력 값이 정렬되어있다는 언급이 없으므로 따로 정렬시켜주도록 합니다.

코드

import sys

N, L = list(map(int, sys.stdin.readline().split()))
pipe = list(map(int, sys.stdin.readline().split()))


def solution():
    fixed = [0] * N
    ans = 0

    # 물 새는 곳 정렬
    pipe.sort()

    for spot in range(N):
        if not fixed[spot]:
            ans += 1
            limit = pipe[spot] + L - 1
            for i in range(spot, N):
                if pipe[i] <= limit:
                    fixed[i] = 1
                else:
                    break

    return ans


print(solution())