[Python] 백준 1449번_수리공 항승

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

1449번: 수리공 항승

 

• 파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샘
• 항승이는 길이가 L인 테이프를 무한개 가지고 있음
• 항승이는 테이프를 이용해서 물을 막으려고 하는데, 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각함
• 물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수 구하기
• 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능

• 입력
  • 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어짐
  • 둘째 줄에는 물이 새는 곳의 위치가 주어짐
  • N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수
• 출력
  • 첫째 줄에 항승이가 필요한 테이프의 개수를 출력
• 시간 제한: 2초
• 메모리 제한: 128 MB

 

"""
입출력 예시)

(예제 입력 1) 
4 2
1 2 100 101
        -> 2

(예제 입력 2)
4 3
1 2 3 4
        -> 2

(예제 입력 3)
3 1
3 2 1
        -> 3
"""

 

 

첫 번째 시도

## 의사코드 ##

# 테이프의 최소 개수 = 물이 새는 곳의 개수(n)을 테이프의 길이(l)로 나눈 값을 올림한 값
# import math 
# math.ceil(n/l)

 

import math 
n, l = map(int, input().split())
point = list(map(int, input().split()))

# 테이프의 최소 개수 = 물이 새는 곳의 개수(n)을 테이프의 길이(l)로 나눈 값을 올림한 값
print(math.ceil(n/l))

-> 틀림

 

• math.ceil() : 올림

import math
print(4 / 3) # -> 1.3333333333333333
print(math.ceil(4/3)) # -> 2

 

 

 

통과한 코드

## 의사코드 ##

# 물이 새는 곳의 위치를 오름차순 정렬
# point.sort()

# start = point[0] # 테이프를 붙인 시작점 
# tape = 1 # 테이프의 개수

# for p in point[1:]:
#     # 현재 위치가 테이프를 붙일 범위 내에 있으면 통과
#     if p in range(start, start+l):
#         continue
#     # 범위 내에 없으면 새로운 테이프 사용, 테이프를 붙인 시작점을 현재 위치로 변경
#     else:
#         tape += 1
#         start = p

 

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

#물이 새는 곳의 위치를 오름차순 정렬
point.sort()

# 테이프를 붙인 시작점 
start = point[0] 
# 테이프의 개수
tape = 1 

for p in point[1:]:
    # 현재 위치가 테이프를 붙일 범위 내에 있으면 통과
    if p in range(start, start+l):
        continue
    # 범위 내에 없으면 새로운 테이프 사용, 테이프를 붙인 시작점을 현재 위치로 변경
    else:
        tape += 1
        start = p 
print(tape)

-> 테이프를 붙인 시작점 변수를 활용해서 현재 위치가 테이프를 붙일 범위 내에 있으면 통과, 그렇지 않은 경우에는 테이프 추가

 

 

• 과정 확인

n=4 
l=2
point = [1, 2, 100, 101]

"""
start: 1
테이프를 붙일 범위: 1 ~ 3
현재 위치: 2
통과 

start: 1
테이프를 붙일 범위: 1 ~ 3
현재 위치: 100
테이프 추가: 2

start: 100
테이프를 붙일 범위: 100 ~ 102
현재 위치: 101
통과 
"""

 

 

 

 

 

참고)

 

https://data-flower.tistory.com/53

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