728x90
#1449
#물이 새는 곳의 개수 n과 테이프의 길이 l을 입력받음
n,l = map(int,input().split())
#물이 새는 위치인 pos를 list에 입력받음
pos = list(map(int,input().split()))
#물이 새는 위치가 정렬이 안되어있을 수 있으니 정렬을 해줌
pos.sort()
#양옆으로 0.5만큼 커버해야하니 start를 pos[0]보다 0.5만큼 왼쪽으로 잡음
start = pos[0] - 0.5
count = 1 #카운터 설정(테이프 개수)
#for문 이용하여 그리디 알고리즘 실행
for i in range(1, len(pos)):
#기존의 테이프로 다음 새는 곳이 커버가 된다면 새로운 테이프 이용
if start + l >= pos[i] + 0.5:
continue
#커버가 안되면 스타트 포인트를 새로 설정해주고 counting 진행
else:
start = pos[i] - 0.5
count += 1
print(count)
기본적으로 타겟인 위치 즉, 구멍의 위치를 특정한 길이의 테이프로 막는 문제인데 여기서의 특이점은 "테이프의 길이를 고려하여 한번에 막을 수 있는 구멍은 한번에 처리하는 것이 좋겠다!"이다. 좌우로 0.5의 여유테이프를 고려하고 붙이되 여유가 충분하여 가까운 구멍까지 막을 수 있다면 테이프를 최대한 아껴보는 것이 관건이다. 그리디 알고리즘을 이용하기 전에 sort function을 활용하여 난잡하게 주어진 구멍 위치 data를 정렬하였다. 그리디 알고리즘 문제들이 그렇듯 list에 찾고자하는 타겟들을 담고 start지점을 설정하고 시작하였다. for문에서 이용된 조건문들은 이 문제를 푸는 핵심이다. start포인트에서 테이프의 길이 사이에 여유있게 막아줄 수 있는 구멍이 있다면 테이프의 숫자를 추가하지 않고 그 다음 구멍을 조사하는 것이다. 만약 테이프의 길이가 충분하지 않다면 새로운 테이프를 추가하고 다음 구멍의 위치를 start포인트로 재설정하고 반복문을 도는 코드이다.
728x90
'Sketch (Programming Language) > Python' 카테고리의 다른 글
Baekjoon Training #1992 (0) | 2022.09.27 |
---|---|
Baekjoon Training #1543 (0) | 2022.09.26 |
Baekjoon Training #1436 (0) | 2022.09.20 |
Baekjoon Training #7568 (2) | 2022.09.20 |
Baekjoon Training #25304 (0) | 2022.09.18 |