[백준] 수리공 항승 1449 (Python)

문제 링크

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

나의 풀이

• 기본적으로 물이 새는 위치를 정렬을 한다.
• start, end 포인터를 사용해 물이 새는 지점을 측정하기 시작한 지점[start]과 현재 항승이 서있는 [end]지점을 비교하며 테이프를 붙일지 안붙이고 한 칸 더 갈지 고민한다.
• 처음, start 는 0, end는 start 다음인 1부터 시작한다. 
  • end는 물이 샌 지점들을 모아놓은 배열의 index이기 때문에 n = 4인 경우, end가 3이 되면 배열의 마지막에 온 것이기 때문에 n-1보다 작거나 같을 때 까지 반복한다.
• end가 n-1보다 작거나 같을 때 까지 while문을 반복한다.
• 3가지 경우를 생각할 수 있다.
  1. 현재 항승이 서 있는 지점과 측정을 시작한 지점의 거리 차이가 항승이 가지고있는 테이프보다 짧은 경우
     • end += 1 을 통해 테이프를 붙이지 않고 항승이는 한 칸을 더 이동한다.
  2. 현재 항승이 서 있는 지점과 측정을 시작한 지점의 거리 차이가 항승이 가지고 있는 테이프와 같은 경우
     • 테이프를 붙이고 start = end+1로, end는 start로 설정한다.
     • while문 마지막에 end+=1이 수행되기 때문에 end를 start + 1이 아닌 start로 설정했다.
     
  3. 현재 항승이 서 있는 지점과 측정을 시작한 지점의 거리 차이가 항승이 가지고 있는 테이프보다 큰 경우
     • 이 경우 항승이는 테이프를 현재 end지점보다 앞에 있는 곳에 테이프를 붙여야 한다.
     • 테이프를 붙이고, start = end로, end = start로 설정한다.
     • 아래 사진의 마지막 단계를 보면 1~4 구간에는 테이프를 붙일 수 없기 때문에, 1~2구간까지 붙이고 다시 4구간부터 새롭게 start포인터를 지정해 탐색한다.

테이프와 같은 경우

• while문이 종료되면 마지막 구간에 테이프를 안붙인 경우가 있을 수 있기 때문에 start를 n과 비교해 start가 더 작으면 테이프를 한 번 붙이고 마무리 한다.

마지막 예외처리

Code

# https://www.acmicpc.net/problem/1449
# 수리공 항승

# start, end 포인터 사용
n,l = map(int,input().split(" "))

water = list(map(int,input().split()))
water.sort()

start = 0
end = 1
answer = 0
idx = 0

if l == 1:
    print(n)

else:
    while end <= n-1:
        if water[end] - water[start] + 1 == l:
            answer += 1
            start = end + 1
            end += 1

        elif water[end] - water[start] +1 > l:
            answer += 1
            start = end
            end = start

        end += 1
    if start < n:
        answer += 1
    print(answer)

Git

https://github.com/youngh0/Algorithm/blob/master/greedy/boj_1449.py