[세그먼트 트리] 백준 12846: 무서운 아르바이트

문제: 성화는 악독하기로 유명한 편의점 사장이다. 그의 편의점에는 특이한 임금 체계를 가지고 있다.

• 각 날마다 일의 차이때문에 일마다 급여가 정해져 있다.
• 돈은 당일에 주지 않고 퇴직을 할 때 한번에 준다.
• 성화는 욕심쟁이라서 해당 일을 한 동안 중 가장 일급이 작을 때를 기준으로 급여를 지급한다.
• 일급이 다른 것을 들키지 않기 위하여 한번이라도 퇴직한 자를 다시 취직 시키지 않는다. (만약 취직을 한다면, 일을 시작 한 날부터 끝날 때까지 하루도 빠지면 안 된다.)

준수는 n+1일 후에 001에 월세를 내야 해서 성화가 사장으로 있는 편의점에 취직하려 한다. 다행히 주변 퇴직자들의 얘기로 급여에 관련해 파악했다. 또한 퇴직자들의 급여 통계를 통해 당장 n일 후까지 일급 정보를 알아냈다. 최대로 많이 일했을 때가 최대 이익이 아닐 수 있다.

어제까지 과제를 제출하고 지금도 001에서 자고 있는 준수를 위해 코딩 잘하는 여러분이 일을 해서 벌 수 있는 최대 이익을 준수에게 알려주도록 하자.

---

입력: 일을 할 수 있는 날의 수 (0 < n ≤ 100000) 가 주어진다.

그 다음 줄 에는 1일부터 n일 까지 일급 Ti 가 순서대로 주어진다. (0 < Ti ≤ 1,000,000)

---

 

n의 값이 적다면, 간단한 반복문을 활용해 답을 낼 수 있는 문제다. 코드는 아래와 같다.

import sys
input = sys.stdin.readline

def find_ans(i):
    ans_list = []
    for j in range(i + 1): # 0부터 i까지
        ans_list.append(min(t[j:i+1]) * (i - j + 1))

    return max(ans_list)

n = int(input()) # 일을 할 수 있는 날의 수
t = list(map(int, input().split())) # 일급의 정보
di = [0] * n
di[0] = t[0]

for i in range(n):
    di[i] = find_ans(i)

print(max(di))

그러나 문제에 주어진 n의 범위는 10만까지. n**2의 시간복잡도를 갖는 해당 코드로는 원하는 시간 내로 문제를 해결할 수 없다.

이 문제를 시간 내에 해결하려면 어떤 알고리즘을 사용해야 할까?

세그먼트 트리를 활용해야 한다.

 

---

세그먼트 트리: 배열과 같은 자료구조에서 특정 구간에 대한 쿼리(자료구조에서 데이터를 검색하는 행위)를 처리하는데 효율적인 자료구조. 주로 배열의 구간 합, 최소값, 최대값 등을 빠르게 계산하는데 쓰인다.

이진트리를 이용해 구현

세그먼트 트리를 활용하면 구간 쿼리를 logN의 시간복잡도로 해결할 수 있다고 한다. 따라서 배열의 크기가 크거나 구간 쿼리를 자주 수행해야 할 때 사용됨

---

import sys
input = sys.stdin.readline

def init(node, start, end):
    if start == end:
        tree[node] = start
    else:
        mid = (start + end) // 2
        left = init(node * 2, start, mid)
        right = init(node * 2 + 1, mid + 1, end)
        if t[left] <= t[right]:
            tree[node] = left
        else:
            tree[node] = right
    return tree[node]

def query(node, start, end, left, right):
    if left > end or right < start:
        return -1
    if left <= start and end <= right:
        return tree[node]
    mid = (start + end) // 2
    left_idx = query(node * 2, start, mid, left, right)
    right_idx = query(node * 2 + 1, mid + 1, end, left, right)
    if left_idx == -1:
        return right_idx
    elif right_idx == -1:
        return left_idx
    else:
        if t[left_idx] <= t[right_idx]:
            return left_idx
        else:
            return right_idx

def solve(start, end):
    if start > end:
        return 0
    idx = query(1, 0, n - 1, start, end)
    ans = t[idx] * (end - start + 1)
    ans_left = solve(start, idx - 1)
    ans_right = solve(idx + 1, end)
    return max(ans, ans_left, ans_right)

n = int(input())
t = list(map(int, input().split()))
tree = [0] * (4 * n)
init(1, 0, n - 1)
print(solve(0, n - 1))