백준 14942(개미), 15678(연세워터파크) 풀이

14942(개미) - P5

# https://www.acmicpc.net/problem/14942

import sys
from collections import defaultdict
from bisect import bisect_left

inp = sys.stdin.readline

N = int(inp())
energy = [int(inp()) for _ in range(N)]
link = defaultdict(list)
visited = [-1] * N
stack = []

for _ in range(N - 1):
    u, v, w = map(int, inp().split())
    link[u - 1].append((v - 1, w))
    link[v - 1].append((u - 1, w))

def dfs(u, cur_sum):
    stack.append((cur_sum, u))
    idx = bisect_left(stack, (cur_sum - energy[u], 0))
    visited[u] = stack[idx][1]
    for v, w in link[u]:
        if visited[v] == -1:
            dfs(v, cur_sum + w)
    stack.pop()

dfs(0, 0)

for i in range(N):
    print(visited[i] + 1)

스택에 지금까지 거쳐온 정점들에 대해 (1번 정점으로부터의 거리, 정점 번호)를 저장하고, 이분 탐색으로 도달 가능한 1번 정점으로부터 가장 가까운 정점을 구할 수 있다. 이 방법은 그래프가 트리 구조이기 때문에 가능하다.

15678(연세워터파크) - P5

# https://www.acmicpc.net/problem/15678

import sys
from heapq import heappush, heappop

inp = sys.stdin.readline

N, D = map(int, inp().split())
K = list(map(int, inp().split()))
heap = []

for i in range(N):
    while heap and heap[0][1] + D < i: # 앞쪽 D만큼의 범위만 탐색
        heappop(heap)
    if heap:
        K[i] -= heap[0][0] # i번째 징검다리에서 끝나는 경우의 최댓값을 저장
    if K[i] > 0: # 양의 값일 경우에만 저장 (앞쪽에 양의 값이 없다면 새로 시작)
        heappush(heap, (-K[i], i))

print(max(K))

회고

14942번 문제는 희소집합(처음 들어봄)으로, 15678번 문제는 세그먼트 트리로 푸는 게 정석인 듯 하지만.. 쉽고 빠르게 풀리면 좋은 거지 괜히 복잡한 알고리즘 쓸 필요 있나 싶다.

한 3달 전까지만 해도 플레 문제는 무서워서 건들지도 못했는데, 이제 정답률 높은 플레 5단계 문제는 꽤 쉽게 풀려서 뭔가 신기하다.