사용자 도구

사이트 도구


ps:problems:boj:1449

수리공 항승

ps
링크acmicpc.net/…
출처BOJ
문제 번호1449
문제명수리공 항승
레벨실버 3
분류

그리디

시간복잡도O(nlogn)
인풋사이즈n<=1000
사용한 언어Python
제출기록30840KB / 72ms
최고기록60ms
해결날짜2022/04/13

풀이

  • 기초적인 그리디 유형
  • 점들을 정렬한 뒤에, 가장 왼쪽점에서부터 순회한다. 가장 왼쪽점에 테이프의 왼쪽 끝을 붙이면, 그 점에서 거리가 L-1 이하인 점들은 모두 지금의 테이프로 커버할수 있으므로 추가 테이프가 필요 없다. 거리가 L-1 이상인 점을 만나면, 새로운 테이프의 왼쪽 끝을 붙이고 반복한다.
  • 시간복잡도는 O(nlogn)

코드

"""Solution code for "BOJ 1449. 수리공 항승".

- Problem link: https://www.acmicpc.net/problem/1449
- Solution link: http://www.teferi.net/ps/problems/boj/1449

Tags: [Greedy]
"""

INF = float('inf')


def main():
    N, L = [int(x) for x in input().split()]  # pylint: disable=unused-variable
    pos_list = [int(x) for x in input().split()]

    left = -INF
    answer = 0
    for pos in sorted(pos_list):
        if pos >= left + L:
            left = pos
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
F I S G J
 
ps/problems/boj/1449.txt · 마지막으로 수정됨: 2022/04/13 15:57 저자 teferi