김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 16637 괄호 추가하기 파이썬(Python)

문제 링크

입력이 작아 완전탐색으로 충분히 풀 수 있는 문제.
그런데 난 DP로 풀었다.
입력의 크기가 최대 19이고 수식의 개수로 따지면 9개이고 9개를 다 묶을 수 있는 것도 아니므로 완전탐색으로도 매우 빠르게 풀 수 있다.
매 연산자마다 해당 연산자를 괄호로 묶는 경우 다음 연산자를 묶을 수 없고, 묶지 않는 경우 다음 연산자를 묶어도 되고 묶지 않아도 된다.
이 규칙에 근거하여 DFS 완전탐색을 하면 최대값을 구할 수 있다.
그런데 나는 처음에 부분문제의 답이 전체 문제의 답을 구성할 것이라 생각했고(후술하겠지만 이게 참은 아니다), 그래서 DP로 접근했다.
사실 중간에 완전탐색을 해도 시간이 충분하겠구나라는 생각은 들었지만 오기가 생겨(아니면 그냥 귀찮아서…) DP로 풀었다.
dp[i]는 i번째로 나타나는 숫자까지 계산했을 때의 최댓값을 의미한다.
점화식은, dp[i]가 dp[i-1]에다가 다음 연산자를 적용한 것(즉 괄호를 묶지 않은 경우)과 dp[i-2]과 다음 연산자로 구성된 식에 이전 연산자를 적용한 것(즉 괄호를 묶은 경우) 중 더 큰 값으로 한다.
예를 들어, 8*3+5는 8*3+5와 8*(3+5) 중 더 큰 값을 답으로 가지는 식이다.
하지만 여기에는 반례가 있는데, 이를테면 9-9-9*2-1 같은 입력이다.
이 식의 최댓값은 9-9-9*(1-2)=9이다.
이 예제의 최댓값을 DP를 이용해 부분문제의 최댓값으로 구성하려고 하면 9-(9-9)*1-2=7이 나온다.
이러한 문제가 발생하는 이유는 부분문제의 최솟값에 음수를 곱하면 그게 최댓값이 될 수 있기 때문이다.
여기에서 착안하여, DP 배열을 2차원으로 구성하여, dp[i][0]은 i번째 숫자까지 계산했을 때 최댓값, dp[i][1]은 i번째 숫자까지 계산했을 때 최솟값으로 두었다.
음수를 곱하면 최솟값이 최댓값이 될 수는 있지만, 중간에 있는 어중간한 값이 최댓값이 되는 것은 불가능하기 때문이다.
이제 dp[i][0]과 dp[i][1]은 dp[i-1][0], dp[i-1][1], dp[i-2][0], dp[i-2][0]의 4가지 경우 중 최댓값과 최솟값이 된다.
이렇게 계산하면, 입력이 작을 때는 완전탐색보다 약간 느릴 수 있지만, 큰 입력에 대해서는 DFS보다 훨씬 빠르게 작동한다.
완전탐색 DFS는 지수 시간 복잡도를 지니지만 상술한 DP는 선형 시간 복잡도를 지니기 때문이다.
이건 엄청난 차이이다. 지수 시간은 입력이 조금만 커져도 엄청난 시간이 걸린다. 10개의 입력에 대해서는 2**10=1024로 준수하지만, 입력이 100개, 그러니까 2**100=1267650600228229401496703205376만 되어도 말도 안 되게 오래 걸린다.
통상적으로 알고리즘 문제에서 1초에 계산 가능한 연산이 10**8개라고 말하는 것을 생각해보면, 저건 풀기 불가능한 것이라고 생각해야 한다.
아무튼, PS는 입력의 크기를 보고 사용할 알고리즘을 결정하는 것 역시 전략이다. 그런 관점에서 DFS 대신 DP로 푼 것은 손실이라고 생각할 수도 있지만, DP가 조금 더 범용적인 입력에 대해 답을 내놓을 수 있음을 생각한다면 그렇게 또 나쁜 건 아닌 것 같다.

#!python

# 정수 a, b와 문자열 op를 넣으면 계산하여 값을 돌려주는 함수
def parse(a, op, b):
    if op == '+':
        return a + b
    if op == '-':
        return a - b
    if op == '*':
        return a * b

n = int(input())

# 표현식에서 피연산자는 정수로, 연산자는 문자열로 저장하였다
exp = [c if i%2 else int(c) for i, c in enumerate(input())]
# dp[i]는 i번째 숫자까지 계산했을 때의 최댓값과 최솟값
dp = [[0, 0] for _ in range(n//2 + 1)]
# dp[0]은 그냥 0번 숫자이므로 그 숫자
dp[0] = [exp[0]] * 2
# dp[1]은 첫번째 연산자이므로 마찬가지로 선택의 여지가 없다
if n >= 3:
    dp[1] = [parse(*exp[0:3])] * 2

# dp 실행
for i in range(2, n//2 + 1):
    # 괄호를 씌우지 않은 경우와 괄호를 씌운 경우, 부분문제의 최댓값을 활용하는 경우와 최솟값을 활용하는 경우, 2*2=4가지 경우를 살펴본다
    dp[i][0] = max(parse(dp[i-1][0], exp[2*i-1], exp[2*i]), parse(dp[i-1][1], exp[2*i-1], exp[2*i]),
                   parse(dp[i-2][0], exp[2*i-3], parse(*exp[2*i-2:2*i+1])), parse(dp[i-2][1], exp[2*i-3], parse(*exp[2*i-2:2*i+1])))
    dp[i][1] = min(parse(dp[i-1][0], exp[2*i-1], exp[2*i]), parse(dp[i-1][1], exp[2*i-1], exp[2*i]),
                   parse(dp[i-2][0], exp[2*i-3], parse(*exp[2*i-2:2*i+1])), parse(dp[i-2][1], exp[2*i-3], parse(*exp[2*i-2:2*i+1])))

# dp 배열의 마지막 원소의 0(최댓값)을 출력한다
print(dp[-1][0])

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑