백준 1449번
https://www.acmicpc.net/problem/1449

문제

후기

⏰ 풀이시간 30분 ++⏰

테이프를 적절히 사용하기 위해서는 우선 정렬이 필요하다고 생각했다.

또한 좌 우로 0.5 만큼을 더 막아야 하니, 이 값들을 list에 저장했고,

set()을 사용하려다가, 다시 정렬이 필요할 것 같아 그냥 list를 사용했다.

테이프의 길이가 1이고, (0.5 , 1, 1.5 ,2) 의 지점에 물이 새고 있다고 했을 때,

0.5 부터 시작해 테이프의 길이만큼 더한 값은 1.5 인데,

그러면 1.5 이하의 모든 지점은 테이프로 막힌다는 알고리즘을 이용했다.

2는 첫 테이프에 막히지 않기 때문에 최종 필요한 테이프는 2개인 식이다.

테이프로 막은 값은 pop 시키며 문제를 해결했다.

나의 풀이

import sys

input = sys.stdin.readline

n, l = map(int,input().split()) #물이 새는 곳의 개수 , 테이프 길이

li = sorted(list(map(int,input().split())))  #물이 새는 위치를 정렬

ans = [] #물이 새는 위치에서 왼쪽으로 0.5, 오른쪽으로 0.5 까지 포함시킨 값의 리스트 


for i in li:
    
    #좌우로 0.5까지 물을 줘야 한다.
    
    a= i-0.5
    b= i
    c= i+0.5
    
    #중복되지 않게 값들을 리스트에 담는다. 
    
    if a not in ans:

        ans.append(a)
    
    if b not in ans:

        ans.append(b)
    
    if c not in ans:

        ans.append(c)

ans.sort()  #정렬 

result = 0 #최종 필요한 개수 

while True:

    if len(ans)==0: #물이 새는곳이 없으면 
        
        print(result) #결과를 출력하고 종료 
        exit()

    cnt=0  # k 테이프로 막힌 만큼 pop 시킬 예정이라, 변수를 하나 만든다. 

    k= ans[0] + l  # 시작한 위치부터, 테이프의 길이만큼 더한 값. k까지 테이프로 막을 수 있게된다. 

    for i in ans:  # 물이 새는곳을 돌면서 

        if i <= k:  # k보다 작은 곳들은 테이프로 막힌다.  

            cnt +=1  #몇개를 pop 시킬지 저장. 
    
    for _ in range(cnt):

        ans.pop(0)


    result +=1