(백준) 1449. 수리공 항승
Python Tip!
-
map(int, input().split())을 통해 int 변환을 한 줄로 깔끔히 처리 해줄 수 있다. 이를 이용해 list로 바로 만들어 줄수도 있음.
-
print('f{variable}') 구문을 통해 JS의 백틱과 같은 효과를 줄 수 있다.
Greedy 문제로, 풀이1은 처음 풀이 시에 길이를 일일이 계산 해 주느라 복잡하게 짰다. 풀이2는 풀이 영상 참고하여 작성했다. 최대 입력 길이인 1001에 해당하는 값을 미리 만들어놓고 반복해 O(N)의 시간복잡도를 가진다. 1억 이상의 입력 길이 시에는 다른 방식을 택하는 게 좋을 듯하다.
풀이 1
K, L = map(int, input().split())
holes = list(map(int, input().split()))
holes.sort()
stack = [] # 구멍 stack
n = 0 # 테이프 갯수
need = 0 # 현재 이어지는 길이
start = holes[0]
for i in holes:
print(f'start = {start}, i = {i}, 길이 = {L}')
if stack:
if start + L > i and start - L < i:
stack.append(i)
need += 1
else:
stack.clear()
stack.append(i)
start = i
need = 1
n += 1
else:
stack.append(i)
start = i
need += 1
if need == L:
stack.clear()
need = 0;
n += 1
if stack:
n += 1
print(n)
풀이 2
K, L = map(int, input().split())
coord = [False] * 1001
for i in map(int, input().split()):
coord[i] = True
ans = 0
x = 0
while x < 1001:
if coord[x]:
ans += 1
x += L
else:
x += 1
Author And Source
이 문제에 관하여((백준) 1449. 수리공 항승), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wngud4950/백준-1449.-수리공-항승저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)