[알고리즘/그리디] 1449번 : 수리공 항승 - python

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

1449번: 수리공 항승

 

---

• 문제
• 소요시간: 30분

---

• 설계하기(접근방법) 

1. 입력받기

구멍의 개수와 테이프의 길이를 입력받는다

 

2. 구현하기

테이프를 잘라서 사용할 수 없으니

중간부터 붙여서 이득을 보는 경우는 없다.

 

그리디하게 앞에서부터 일단 붙여나가야 한다

 

리스트를 정렬해주고 테이프를 앞에서부터 붙인다

 

첫번 째 구멍부터 테이프를 붙인다

그러면 테이프 끝의 위치는

구멍 + 테이프의 길이가 될 것이다

 

현재 구멍보다 테이프 끝의 위치가 큰 경우 pass한다

 

현재 구멍보다 테이프의 위치가 작거나 같은 경우,

테이프의 길이가 모자란 것이니

 

현재 구멍 + 테이프의 길이로 초기화 해준 후

테이프를 사용한 개수를 +1 해준다

 

3. 출력하기

사용한 총 테이프의 개수를 출력한다

 

---

• 코드(출력)

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

location.sort()

cnt = 0
tape = location[0]
for i in location:
    if tape <= i:
        cnt += 1
        tape = (i + l)

print(cnt)

---

• 얻어갈 부분

1. 구멍의 위치를 제거해 나가려다가, 테이프의 위치와 구멍의 위치만 비교하면 된다는 것을 깨닫고 코드를 변경했다.