alpyrithm_알파이리즘

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

Algorithm/백준 알고리즘_Python

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

알파이 2020. 8. 14. 08:47

 

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

 

1449번: 수리공 항승

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

www.acmicpc.net

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

풀이 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)

 

 

 

 

 

728x90
반응형
Comments