[백준 1449번 문제, 파이썬] 수리공 항승

문제

문제

항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

항승이는 길이가 L인 테이프를 무한개 가지고 있다.

항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

입력

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.

---

코드

n, l = map(int, input().split(' '))
line = list(map(int, input().split(' ')))
line = sorted(line)

answer = 0
left_position = line[0] - 0.5

for i in line:
    right_position = i + 0.5
    if left_position < right_position:
        left_position = i + l - 0.5
        answer += 1

print(answer)

---

해결

예를들어 파이프에 5개의 구멍이 있고 테이프의 길이는 1이라고 하자

그리고 1, 2, 3, 4, 5 x 좌표에 구멍이 났다고 하자

 

수리공 성격에는 구멍난곳 좌우로 0.5 만큼은 테이프를 붙여야한다고 하니

 

수리공이 갖고있는 테이프의 길이는 1 즉 구멍난곳 모두 테이프 하나로 막아야한다

 

이러한 경우는 어떤가

 

테이프의 길이가 2라서 1, 2좌표의 구멍을 막을 수 있다.

 

그러면 어떻게 풀어야할까

 

먼저 테이프를 칠할 시작 기준점(left)을 정해주자 처음 시작이니까 현재 0번째 인덱스의 요소 - 0.5 지점에 하면 되겠다

그리고 현재 요소를 테이프로 막는 위치는 요소의 + 0.5 지점(right)으로 매번 지정해주자

 

 

테이프를 한번 칠해볼까?

 

 

0.5에서 테이프길이 2를 더하면 2.5. 0.5에서 2.5까지 테이프가 칠해졌다.

아직 for문에서 1번이고 테이프를 칠한 마지막 위치 = 이제 테이프를 칠할 위치 기준점(left)는

테이프 길이만큼 칠하고 - 0.5 위치 이다.

 

그래서 1에서 2만큼 칠하면 3 거기다가 -0.5 해주면 2.5가 left가 되는거다!

 

그럼 2 지점은 테이프를 칠해야할지 아닌지 확인해볼까?

 

 

이미 1번 구멍에서 2까지 테이프를 칠했으니 칠할필요가 없다

이렇게 left < right 조건이면 칠하는걸로 한다면 테이프를 칠해야하는지 아닌지 알수있다

 

그러면 3은 테이프를 칠해야하는지 볼까?

 

 

left < right 조건에 맞는다 그러면 칠해야지

 

 

그러면 이렇게 테이프 2개를 사용해서 1, 2, 3, 4 를 전부 칠했다!

 

---

참고

링크