[백준] [그리디] 1449. 수리공 항승

1449. 수리공 항승

1449번: 수리공 항승

 

• 내 풀이
  • 물이새는곳의 전후값 차이를 더해가면서 그 합이 (테이프길이 -1) 보다 길어지면 테이프+1
    • -> 전후값 차이를 바로 기준값에서 빼는 식으로 하는게 더 좋음
  • 순서대로 들어오지 않을 수 있으니 sort
  • 맨마지막에 가장 큰 수 넣어서 마지막 테이프까지 +1되도록
    
    
• 처음부터 1개로 세주는 경우

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

lst.sort()
result=1
tmp=l-1
for i in range(1,n):
    tmp-=lst[i]-lst[i-1]

    if tmp<0: 
        result+=1
        tmp=l-1


print(result)

 

 

• 마지막에 큰 수 넣어서 마지막 구멍까지 확인하는 경우
  • for문 범위를 n+1 까지 하는것 주의

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

lst.sort()
lst.append(int(1e9))
result=0
tmp=l-1
for i in range(1,n+1):
    tmp-=lst[i]-lst[i-1]

    if tmp<0: 
        result+=1
        tmp=l-1


print(result)