[Python] 백준 1449번 : 수리공 항승

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

1449번: 수리공 항승

---

 문제 풀이

그리디 문제이다. 문제에서 좌우 0.5 간격 어쩌고 쓰여있지만 정수만 주어지기 때문에 딱히 신경쓰지 않아도 괜찮다.

확인하는 값(arr[0])부터 테이프의 길이 - 1 (L - 1) 까지는 하나로 수리할 수 있으니

확인 값부터 테이프의 길이만큼 해당하는 값들을 배열에서 빼주고 값을 하나 추가하면 된다.

 

예를 들어 테이프의 길이가 3이고 물이 새는 곳이 1, 2, 3, 4, 5 일 때

1을 확인할 때 1, 2, 3을 지워지고 다음 값인 4를 확인할 때 4, 5, 6이 지워져서 2가 정답이 된다.

 느낀 점

사실 그리디 알고리즘을 생각했을 때 크게 어려운 문제는 아니다.

또 사실 길이가 1일 때는 따지지 않아도 상관없는데 그냥 썼다.

 코드

import sys

n, l = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
cnt = 0

if l == 1: 
    print(len(arr))
    sys.exit(0)
while len(arr) != 0:
    tmp = arr[0]
    cnt += 1
    for i in range(l):
        if tmp+i in arr: arr.remove(tmp+i)
        
print(cnt)