[알고리즘][Python] 백준(BOJ) 1449 수리공 항승_파이썬

 

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

1449번: 수리공 항승

 

 

 

 

 

 

 

문제 풀기 전 공부할 것 : 정렬, 반복문

 

 

 

 

 

 

 

풀이 1

<내용>

• 새는 곳 위치 한 곳을 막기 위해서는 길이가 1인 테이프 1개가 필요하다.
• 새는 곳의 위치부터 테이프를 붙였다면 테이프의 길이만큼 떨어진 곳까지 막을 수 있다.
• 새는 곳의 위치를 오름차순으로 정렬한다.
• 새는 곳의 위치는 자연수이므로 1로 초기화를 하고 현재 막을 수 있는 곳도 leak의 0번째(새는 곳의 가장 작은 위치)에서 테이프의 길이만큼 더한 곳을 r로 초기화한다.
• for문으로 leak의 index가 1인 곳부터 돌면서 테이프로 이미 막혀있는 곳은 continue 하고 아니라면 테이프를 하나 더 붙여 cnt에 1을 더하고 r의 값을 새로 정정한다.

 

 

<코드>

n, l = map(int, input().split())
leak = list(map(int, input().split()))
leak.sort()
cnt = 1
r = leak[0] + (l-1)
for i in range(1, n):
    if leak[i] <= r:
        continue
    cnt +=1
    r = leak[i] + (l-1)
    
print(cnt)

 

 

+) 문제에서 새는 곳의 위치는 자연수이기 때문에 최소 1곳이 존재하지만 그렇지 않은 경우를 대비해 cnt = 0으로 초기화하여 해결하는 방법을 찾기

 

 

 

 

 

 

 

풀이 2

<내용>

• 위의 풀이와 유사하나 처음 초기화에서 차이가 있다.
• 새는 곳의 위치를 0으로 초기화를 하고 현재 막을 수 있는 곳도 0으로 r을 초기화한다.
• for문으로 leak를 돌면서 테이프로 이미 막혀있는 곳은 continue하고 아니라면 테이프를 하나 더 붙여 cnt에 1을 더하고 r의 값을 새로 정정한다.

 

 

<코드>

n, l = map(int, input().split())
leak = list(map(int, input().split()))
leak.sort()
cnt = 0
r = 0
for i in range(n):
    if leak[i] <= r:
        continue
    cnt +=1
    r = leak[i] + (l-1)
    
print(cnt)