alpyrithm_알파이리즘
[알고리즘][Python] 백준(BOJ) 1449 수리공 항승_파이썬 본문
1449 수리공 항승 https://www.acmicpc.net/problem/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)
728x90
반응형
'Algorithm > 백준 알고리즘_Python' 카테고리의 다른 글
[알고리즘][Python] 백준(BOJ) 1747 소수&팰린드롬_파이썬 (0) | 2020.08.17 |
---|---|
[알고리즘][Python] 백준(BOJ) 1205 등수 구하기_파이썬 (0) | 2020.08.15 |
[알고리즘][Python] 백준(BOJ) 1946 신입 사원_파이썬 (0) | 2020.08.13 |
[알고리즘][Python] 백준(BOJ) 8979 올림픽_파이썬 (0) | 2020.08.07 |
[알고리즘][Python] 백준(BOJ) 2816 디지털 티비_파이썬 (0) | 2020.08.05 |
Comments