백준 1449 수리공 항승 Python 3

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

1449번: 수리공 항승

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1449.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
def get_tape_cnt(L, leaks):
    tape_start = leaks[0]-0.5
    cnt = 0
    for l in leaks:
        if tape_start < l < tape_start+L:
            continue
        cnt += 1
        tape_start = l-0.5
    return cnt+1

input = sys.stdin.readline
N, L = map(int, input().split())
leaks = list(map(int, input().split()))
leaks.sort()
print(get_tape_cnt(L, leaks))

---

풀이 과정

풀이 시간 30분

길이가 L인 테이프를 사용해서 물이 새는 곳을 모두 막을 때, 필요한 테이프의 최소 개수를 구하는 문제이다.

이때, 물이 샌 곳을 막기 위해서는 좌, 우로 0.5 떨어진 곳으로부터 테이프가 붙여있어야 한다.

따라서 나는 물이 샌 좌표를 오름차순으로 정렬한 후, 맨 왼쪽부터 차례대로 테이프를 붙여나가며 개수를 세어 나갔다.

tape_start 변수를 통해서 테이프를 붙인 시작점을 나타내었고, 첫 시작점은 물이 샌 첫 지점의 -0.5 좌표로 지정했다.

 

import sys
def get_tape_cnt(L, leaks):
	#테이프의 첫 시작점
    tape_start = leaks[0]-0.5
    #필요한 테이프의 개수
    cnt = 0
    
    for l in leaks:
    	#현재 지점 l이 테이프를 붙일 곳에 포함되는 경우, 다음 물이 샌 좌표를 탐색한다
        if tape_start < l < tape_start+L:
            continue
            
        #현재 지점 l이 테이프를 붙인 범위에 포함되지 않은 경우,
        #이전 물이 샌 범위까지만 테이프를 붙여준다
        cnt += 1
        #현재 지점보다 왼쪽으로 0.5 떨어진 범위부터 다시 테이프를 붙여나갈 범위를 탐색한다
        tape_start = l-0.5
        
    return cnt+1

input = sys.stdin.readline
N, L = map(int, input().split())
leaks = list(map(int, input().split()))
leaks.sort()
print(get_tape_cnt(L, leaks))

#시간복잡도 = O(Nlog N), 공간복잡도 = O(N)