[백준/파이썬] 1449번 수리공 항승 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1449번 수리공 항승
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

상단 링크 참조

코드

n, l = map(int, input().split())

pl = list(map(int, input().split()))

pl.sort()

cnt = 0

tmp = 0
for p in pl:
    if tmp < p:
        cnt += 1
        tmp = p + l - 1

print(cnt)

설명

쉬운 그리디 알고리즘 문제입니다.

그리디 알고리즘이란, 매 순간마다의 최적해가 전체의 최적해가 되는 알고리즘으로, 실생활에서 이를 응용할 수 있는 문제는 그다지 없고 특수한 경우에만 적용 가능합니다.

이런 경우가 그 예로, 구멍난 곳을 오름차순으로 우선 정렬해줍니다.

이후, 현재 마지막으로 막은 위치 tmp 변수에 구멍이 날때마다 테이프를 붙이고, 테이프의 길이 - 여유분길이만큼씩 더해줍니다.

이 과정에서 이미 테이프가 붙어있는 곳이라면 무시하면 되겠죠? 그래서 tmp < p 라는 조건을 사용했습니다.

---

• 백준 문제풀이 전체 목록 보기

---