[백준/Python] 1541 : 잃어버린 괄호

 

얼핏 보기엔 쉬워보이지만 "괄호를 적절히 쳐서 이 식의 값을 최소로 만든다" 는 개념을 정확히 이해하고 구현 방법을 떠올려야 풀 수 있는 문제였다.

결론적으로 말하면 식을 최소로 만드는 방법은 입력식에서 - 기호를 기준으로 사이에 있는 숫자들을 모두 더해서 빼주면 된다는 뜻이다.

 

예를 들어 55 - 10 + 20 - 30 + 40 + 50 와 같은 식이 주어졌다고 가정해보자.

이 상태에서 괄호를 적절히 쳐서 최소값을 만들어 내는 것이 목표이다. 

뺄셈 하는 방법을 다시 생각해보면 100 - 30 보다 100 - 70 이 더 작은 것과 같이, 최솟값은 빼는 숫자가 최대일수록 결과값을 작아져서 최솟값이 완성되는 것이다.

즉 같은 말을 더 구체화 해보자면 100 - (2 + 18) 보다 100 - (40 + 30) 이 더 작은 셈이고, 다시 말하지만 후자인 '빼는 숫자'가 최대일 때 최솟값이 도출되므로 100 - 2 + 18 보다 100 - (2 + 18) 이 더 작은 셈이다.

따라서 뺄셈 '-' 기호를 기준으로 식을 분리하면 분리된 식에는 각각 더하기 기호로 묶인 다항식만 남게되고, 이들이 각 괄호 안에 들어가서 결론적으로는 뺄셈을 수행하게 될 아이들이다.

 

이를 바탕으로 앞서 가정한 식을 뺄셈을 기준으로 분리해보면 다음과 같다.

55 - 10 + 20 - 30 + 40 + 50

55 - (10 + 20) - (30 + 40 + 50)

55 - 30 -120

-95 가 최솟값!

 

이러한 이해를 바탕으로 코드를 작성할 때 적용해야 할 단계는 다음과 같다.

1. split을 통해 식을 '-' 기호를 기준으로 분리

2. 나뉘어진 '+'기호로만 이루어진 다항식들을 하나씩 순회하며 방문

3. 해당 다항식에서 '+'기호로 분리하면 숫자들만 나오는데, 이들은 현재 다항식에서는 '+' 기호로 묶여있던 애들이지만 어차피 해당 다항식 전체가 괄호로 묶여 앞에 있는 숫자와 뺄셈을 하게될 운명이기 때문에 전체 숫자에서 빼주어 최솟값을 완성해나간다.

 

arr = input().split('-') 
cnt = 0
for i in arr[0].split('+'):
    cnt += int(i)
for lst in arr[1:]:
    for j in lst.split('+'):
        cnt -= int(j)

print(cnt)

 

앞서 소개한 개념과 과정을 적용하면 위와 같은 코드를 도출할 수 있다.

처음에는 그냥 for문만 썼었는데 계속 에러가 발생해서 찾아보니 첫 번째는 - 로 시작하는 경우의 수 때문에 따로 작업해야 해결이 된다 하여 입력 arr를 arr[0] 와 arr[1:] 로 각각 나누어 arr[0]부분은 따로 처리해주었더니 해결되었음

 

 

사실 너무 많은 에러와 시행착오를 거쳐서 사실상 구글링으로 백만번 수정한 후에 해결한 문제긴 하다...

고작 짧은 코드를 작성하는데에도 골머리를 앓는것을 보니 실력이 아직도 부족하여 더 연습을 열심히 해야될 것 같다...!!