[BaekJoon] 백준 1541번 잃어버린 괄호

[BaekJoon] 백준 1541번 잃어버린 괄호

 

문제: https://www.acmicpc.net/problem/1541

 

괄호를 쳐서 최소값이 나오게 만들라는 문제였다. 

예시를 보면 55-50+40 의 경우 (55-50+40)이면 45이지만 55-(50+40)이면 -35이다. 이렇게 괄호 위치에 따라 값이 달라질 수 있다.

 

우선 별다른 알고리즘이 생각나지 않아 규칙을 생각해보았다.

식이 주어졌을 때, - 뒤의 계산값이 크면 클수록 좋고, - 앞의 계산값은 작으면 작을 수록 우리가 원하는 값이 나온다.

 

두가지로 경우를 나눌 수 있다. (연속으로 같은 연산자가 나올 수 없기 때문)

 

먼저 -가 먼저 나올 경우 80-30+20-30 이와 같이 나오면 80-(30+20)-(30) 이와 같이 괄호를 치면 모두 음수가 되서 가장 작은 값이 나온다.

 

두번째로 +가 먼저 나올 경우 80+30-20+30 이와 같이 나오면 (80+30)-(20+30) 이면 최소다. 

 

결국 두 경우로 나눠서 계산해주면 되는 별도의 알고리즘이 필요없는 문제였다. 다만 이것을 생각해내는데 어려울 수 있다고 생각한다.

 

정리하자면

1. -를 기준으로 나눠준다.
2. 나눈 값들을 각각 계산(더해)준다.
3. 가장 앞의 값에서 뒤에 값들을 전부 빼준다.

 

arr = input().split("-")
results = []
for i in arr:
    cnt = 0
    b = i.split("+")
    for j in b:
        cnt += int(j)
    results.append(cnt)
first = results[0]
for i in range(1, len(results)):
    first -= results[i]
print(first)