Algorithm/Greedy

[Greedy] 백준 1541번 “잃어버린 괄호” Python 풀이

운호(Noah) 2022. 11. 2. 18:15

문제 링크

풀이

  • 최솟값을 만들기 위해서는 - 기준으로 괄호를 치면 됩니다.
  • 예를 들어, 55 - 50 + 40 - 30 + 20 을 입력 받았을 때,
  • - 기준으로 괄호를 친다면,
  • 55 - (50 + 40) - (30 + 20) 가 되며, 이는 최솟값이 됩니다.
  • 세부 알고리즘은 아래 코드와 같으며,
  • ['55', '50 + 40', '30 + 20']로 전처리했을 때,
  • 각 원소들을 원소들의 합으로 변환한 뒤,
  • 맨 처음의 원소는 더하고 나머지 원소들은 빼주면 됩니다.

코드

import sys

# 입력 문자열
input_ = sys.stdin.readline().rstrip()

# 숫자 배열
num_arr = []

# 입력 문자열을 - 를 기준으로 분리
arr = input_.split('-')

# 각 원소들을 원소들의 합으로 변환
for element in arr:

    # 현재 원소를 + 를 기준으로 분리한 뒤, 원소들의 합으로 변경
    temp = 0
    for num in element.split('+'):
        temp += int(num)

    # 숫자 배열에 삽입
    num_arr.append(temp)

# 숫자 배열에서, 맨 처음의 원소는 더하고 나머지 원소들은 뺍니다.
result = num_arr[0]
for i in range(1, len(num_arr)):
    result -= num_arr[i]

print(result)

참고