[PS] BOJ 25711 / 인경산

Minjun Kim

09 Nov 2025 • 6 min read

Thumbnail: Photo by Mads Schmidt Rasmussen (Unsplash)

문제 링크: https://www.acmicpc.net/problem/25711

누적 합을 어떻게 활용할 지 잘 생각해야 합니다.

풀이

누적 합 계산하기

문제에서는 $Q$개의 질문이 주어지고, 각 질문마다 $i$번 산장에서 출발해 $j$번 산장에 도달하기 위해 소모되는 체력을 계산해야 합니다. 매 질문마다 거리를 직접 계산하는 방식으로는 질문을 처리하는 과정의 시간 복잡도가 $O(NQ)$가 되어 시간 초과를 받습니다. 따라서, 각 질문을 더 빨리 풀기 위한 방법이 필요합니다.

$i$번 산장에서부터 $j$번 산장에 도달하기 위해 소모되는 체력을 구하는 것이 질문의 내용인데, 이는 연속된 거리의 합이므로 누적 합을 통해 사전에 계산해둘 수 있습니다.

두 방향의 누적 합

문제 조건을 보면, 임의의 두 산장 사이를 오갈 때 소모되는 체력은 다음과 같습니다.

오르막길인 경우, 거리의 3배
평지인 경우, 거리의 2배
내리막길인 경우, 거리만큼

def calculate_health(prev_y, cur_y, distance):
    height_diff = cur_y - prev_y
    if height_diff == 0:
        return distance * 2
    elif height_diff > 0:
        return distance * 3
    else: # height_diff < 0
        return distance

인접한 두 산장 사이를 오갈 때 소모되는 체력을 계산해주는 함수 (거리는 미리 계산)

오르막길과 내리막길은 이동하는 방향에 따라 달라지게 됩니다. $i$가 $j$보다 작을 때 오르막길이었던 길은 $i$가 $j$보다 클 때 내리막길이 됩니다. 따라서, 두 방향 ($i < j$, $i > j$)의 누적 합을 모두 계산해주고 주어진 $i, j$에 맞게 사용하면 됩니다.

X = list(map(int, input().split()))
Y = list(map(int, input().split()))

prefix_health = [0] * N # x좌표가 증가하는 방향으로 이동시의 누적 합
reversed_prefix_health = [0] * N # x좌표가 감소하는 방향으로 이동 시의 누적 합

for idx in range(1, N):
    distance = sqrt((X[idx] - X[idx - 1]) ** 2 + (Y[idx] - Y[idx - 1]) ** 2)
    prefix_health[idx] = prefix_health[idx - 1] + calculate_health(Y[idx - 1], Y[idx], distance)

    rev_idx = N - 1 - idx
    distance = sqrt((X[rev_idx + 1] - X[rev_idx]) ** 2 + (Y[rev_idx + 1] - Y[rev_idx]) ** 2)
    reversed_prefix_health[rev_idx] = reversed_prefix_health[rev_idx + 1] + calculate_health(Y[rev_idx + 1], Y[rev_idx], distance)

두 방향의 누적합 계산

전체 코드

from math import sqrt
input = open(0).readline

N, Q = map(int, input().split())

def calculate_health(prev_y, cur_y, distance):
    height_diff = cur_y - prev_y
    if height_diff == 0:
        return distance * 2
    elif height_diff > 0:
        return distance * 3
    else: # height_diff < 0
        return distance

X = list(map(int, input().split()))
Y = list(map(int, input().split()))

prefix_health = [0] * N # x좌표가 증가하는 방향으로 이동시의 누적 합
reversed_prefix_health = [0] * N # x좌표가 감소하는 방향으로 이동 시의 누적 합

for idx in range(1, N):
    distance = sqrt((X[idx] - X[idx - 1]) ** 2 + (Y[idx] - Y[idx - 1]) ** 2)
    prefix_health[idx] = prefix_health[idx - 1] + calculate_health(Y[idx - 1], Y[idx], distance)

    rev_idx = N - 1 - idx
    distance = sqrt((X[rev_idx + 1] - X[rev_idx]) ** 2 + (Y[rev_idx + 1] - Y[rev_idx]) ** 2)
    reversed_prefix_health[rev_idx] = reversed_prefix_health[rev_idx + 1] + calculate_health(Y[rev_idx + 1], Y[rev_idx], distance)

for _ in range(Q):
    i, j = map(int, input().split())
    if i <= j:
        # 칸을 기준으로 누적 합을 계산했으므로, i번째 칸 ~ j-1번째 칸까지의 합을 계산한다.
        dist = prefix_health[j - 1] - prefix_health[i - 1]
    else:
        # 칸을 기준으로 누적 합을 계산했으므로, i - 1번째 칸 ~ j번째 칸까지의 합을 계산한다.
        dist = reversed_prefix_health[j - 1] - reversed_prefix_health[i - 1]
    print(f"{dist:f}")

solution.py

시행착오

누적 합이 2개 필요

처음엔 한 개의 누적 합으로 계산하려고 했었는데, 방향에 따라 오르막길/내리막길의 여부가 달라진 다는 것을 뒤늦게 깨달았습니다. 누적 합을 각 방향에 맞게 2개 계산해서 질문마다 적합한 누적 합을 사용해 해결했습니다.

소수 정밀도 문제

누적 합 계산 과정에서, 소수 값을 계속해서 더하게 되면 오차가 커질 수 있습니다. 이를 우려해 decimal모듈을 사용해 float보다 더 정밀한 소수 표현을 사용하려 했으나, 이 경우 정답 코드와 자료형만 다를 뿐인데 시간 초과를 받았습니다. 이는 decimal모듈을 활용한 연산 속도가 float기반의 연산보다 느리기 때문입니다.

float의 경우, 하드웨어 단에서 부동 소수점 연산을 수행합니다. 하지만, decimal.Decimal의 경우는 보다 정확한 계산을 위해 내부적으로 십 진수를 활용하고, 연산 또한 소프트웨어 단에서 이루어집니다. 연산 과정의 차이로 인해 두 방식의 속도 차이가 발생합니다.

PS와 같이 시간 제한이 빠듯한 경우에는 decimal 모듈보단 Python의 내장 부동 소수점 타입인 float를, 정밀도가 요구되는 경우에는 decimal모듈을 사용하면 됩니다.

from decimal import Decimal
input = open(0).readline

N, Q = map(int, input().split())
DECIMAL_SQRT = Decimal("0.5")

def calculate_health(prev_y, cur_y, distance):
    height_diff = cur_y - prev_y
    if height_diff == 0:
        return distance * 2
    elif height_diff > 0:
        return distance * 3
    else: # height_diff < 0
        return distance

X = list(map(Decimal, input().split()))
Y = list(map(Decimal, input().split()))

prefix_health = [0] * N # x좌표가 증가하는 방향으로 이동시의 누적 합
reversed_prefix_health = [0] * N # x좌표가 감소하는 방향으로 이동 시의 누적 합

for idx in range(1, N):
    distance = ((X[idx] - X[idx - 1]) ** 2 + (Y[idx] - Y[idx - 1]) ** 2) ** DECIMAL_SQRT
    prefix_health[idx] = prefix_health[idx - 1] + calculate_health(Y[idx - 1], Y[idx], distance)

    rev_idx = N - 1 - idx
    distance = ((X[rev_idx + 1] - X[rev_idx]) ** 2 + (Y[rev_idx + 1] - Y[rev_idx]) ** 2) ** DECIMAL_SQRT
    reversed_prefix_health[rev_idx] = reversed_prefix_health[rev_idx + 1] + calculate_health(Y[rev_idx + 1], Y[rev_idx], distance)

for _ in range(Q):
    i, j = map(int, input().split())
    if i <= j:
        # 칸을 기준으로 누적 합을 계산했으므로, i번째 칸 ~ j-1번째 칸까지의 합을 계산한다.
        dist = prefix_health[j - 1] - prefix_health[i - 1]
    else:
        # 칸을 기준으로 누적 합을 계산했으므로, i - 1번째 칸 ~ j번째 칸까지의 합을 계산한다.
        dist = reversed_prefix_health[j - 1] - reversed_prefix_health[i - 1]
    print(f"{dist:f}")

decimal 모듈을 활용한 코드. 시간 초과를 받는다.