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

[백준] 1449번 - 수리공 항승

1) 문제 해결 아이디어

아이디어는 쉽게 떠올릴 수 있는 문제였다.

물이 새는 곳의 위치 기준 좌우 0.5 길이 즉, 테이프 길이 1인 테이프 1개로 막을 수 있다.

좌우 0.5이지만 편의상 새는 곳 위치 기준 우측으로 길이 1만큼 막는다고 풀어도 같은 결과가 나온다.

 

먼저, 새는 곳 위치(loc)를 올림차순 정렬한다. (왼쪽부터 새는 곳을 차례로 막기 위함)

 

첫번째 새는 곳은 무조건 새로운 테이프를 써서 막아야 하기 때문에

테이프 수(cnt)를 1로 초기화 하고 테이프 끝 지점(tape_end)를 새는 곳 위치(loc[0]) 에서 테이프 길이(l)만큼 더한 값으로 초기화 한다.

 

나머지 새는 곳의 위치에 대하여 for문을 돌린다.

현재 새는 곳 위치의 끝지점이 최근 붙여진 테이프의 끝 지점보다 크다면 새로운 테이프를 이용해야하므로

테이프 개수(cnt)를 증가시키고 테이프 끝 지점(tape_end)를 갱신한다.

 

2) 소스코드

n, l = map(int, input().split())  # 새는 곳 수, 테이프 길이
loc = list(map(int, input().split()))  # 새는 곳 위치
loc.sort() # 올림차순 정렬

cnt = 1  # 테이프 수
tape_end = loc[0] + l  # 최근 테이프 끝 지점 갱신
for i in range(1, n):
  # 최근 테이프 끝 지점이 현재 위치의 끝 지점보다 작거나 같으면
  if(loc[i] + 1 > tape_end):
    # 새로운 테이프 붙이기
    tape_end = loc[i] + l  # 테이프 끝 지점 갱신
    cnt += 1  # 테이프 개수 증가

print(cnt)