백준 나무자르기 문제이다. 해당 문제는 이진 탐색을 통해 풀어야 시간초과가 나지 않는다.
import sys
input = sys.stdin.readline
# n: 나무의 수, m: 필요한 나무 길이
n, m = map(int, input().split())
tree = list(map(int, input().split()))
# 이분 탐색의 탐색 범위: 최소 1부터 가장 큰 나무의 높이까지
start, end = 1, max(tree)
# 적절한 절단 높이를 찾기 위한 이분 탐색
while start <= end:
mid = (start + end) // 2 # 현재 설정할 절단기 높이 (중간값)
total = 0 # 잘린 나무 총 길이 계산
for i in tree:
if i >= mid:
total += i - mid # mid보다 큰 나무만 잘림
# 필요한 나무 길이 m보다 많이 잘렸으면 절단 높이를 더 높여도 됨
if total >= m:
start = mid + 1
# 너무 적게 잘렸으면 절단 높이를 낮춰야 함
else:
end = mid - 1
# 최종적으로 end는 나무를 m만큼 가져갈 수 있는 가장 높은 절단기 높이
print(end)아이디어
- 절단 높이 H를 기준으로 모든 나무를 잘랐을 때 얻는 나무 길이의 총합을 비교
- 이 길이가 M 이상이면 더 높은 절단 높이도 가능하므로 H를 더 높히기
- 그렇지 않으면 H 낮추기
- H를 이분 탐색으로 조절해가며 최적의 절단 높이 찾기
알고리즘
- 입력값을 받아 나무들의 높이를 리스트로 저장
- 절단기 높이의 탐색 범위는 1부터 가장 큰 나무의 높이까지로 설정
- mid를 기준으로 모든 나무를 순회하며 잘린 길이의 총합 구하기
- 총합이 M 이상이면 start = mid + 1, 아니면 end = mid - 1.
- 이 과정을 반복하면 최적의 절단 높이 H
시간복잡도
- 이분 탐색은 log2(max(tree)) 만큼 반복
- 각 반복마다 모든 나무를 순회 (O(N)).
- 시간복잡도는 O(N log M) 수준으로 매우 효율적
import sys
input = sys.stdin.readline
n = int(input())
stack = [] # 타워 인덱스 저장
towers = list(map(int, input().split())) # 타워의 높이와 순서
result = [0] * n # 결과를 저장할 리스트 (초기값은 전부 0)
for i in range(n):
# 현재 타워보다 낮은 타워는 레이저를 받을 수 없으므로 제거
while stack and towers[stack[-1]] < towers[i]:
stack.pop()
if stack:
# 스택이 비어 있지 않으면 → 현재 타워의 레이저가 닿는 타워가 있음
# stack[-1]은 레이저를 수신하는 가장 가까운 왼쪽 타워의 인덱스
result[i] = stack[-1] + 1 # +1은 문제에서 인덱스가 1부터 시작하기 때문
else:
# 스택이 비어 있으면 → 왼쪽에 자신보다 높은 타워가 없음 → 0 (기본값 유지)
pass
# 현재 타워의 인덱스를 스택에 추가
# 이후 들어올 타워들의 레이저 수신 여부를 판단할 기준이 됨
stack.append(i)
# 결과 출력 (리스트를 언팩하여 공백 구분으로 출력)
print(*result)아이디어
- 단순히 이중 반복문으로 매번 왼쪽을 탐색하면 시간초과(O(N^2)).
- "자신보다 높은 탑"을 효율적으로 찾기 위해 스택을 사용
- 스택에는 탑의 인덱스를 저장하고, 조건을 만족하지 않는 탑은 pop하여 제거
알고리즘
- 타워들을 순서대로 탐색하면서 현재 탑의 왼쪽에 있는 탑들 중 자신보다 높은 탑을 찾기
- 인덱스를 저장하는 스택을 사용
- 스택에 저장된 인덱스 중 가장 최근의 값(stack[-1])이 현재 탑보다 작으면 pop하여 제거
- 스택이 존재하면 top 값이 현재 탑이 레이저를 처음 맞는 대상임
- 매 탐색 후 현재 인덱스를 스택에 추가
시간복잡도
- 각 탑은 한 번씩 push/pop 되므로 O(N)
- 매우 효율적인 스택 기반 선형 시간 알고리즘
나무 쓱싹쓱싹