백준 - 16637번 괄호 추가하기

문제

수식이 들어올 때 아래 규칙을 지키면서 괄호를 추가한다
괄호 안에는 연산자가 하나만 들어있어야 한다
중첩된 괄호는 사용할 수 없다
괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하자!

생각

뭔가 앞에서 쭈욱 괄호 추가해봤다가 안 해봤다가 하면서 최대값을 구하는 것 같아서
이건 재귀로 푸는 문제네! 라는 생각은 빨리 했는데

내가 재귀를 싫어하기도 하고, 문자열 문제도 싫어하기도 하구..
그래서 익숙치 않아서 코드 짜는데 쫌 해맸다

처음 푼 방법

앞에 두 숫자가 먼저 계산될 때,
앞에 말고 뒤에 두 숫자가 먼저 계산될 때,
이렇게 두 상황이 있는 건 알겠는데 재귀 함수를 어떻게 짜지?

처음에는 괄호 안에 있는 애들을 타고 타고 들어가서
계산하고 return return 하는 식으로 해서 마지막에 최댓값 받아야지~ 하고

def dfs(index):
    # index가 끝에 도달했을 때 처리

    # case별로 결과 구하고
    case1 = ...
    case2 = ...

    # 최대값 받아야지~~
    return max(case1, case2)
    
print(dfs(0))

이렇게 해야지 했는데, 생각해보니 마지막에 max값을 받는건 좋은데,
중간에 크게 만들다가 크게 마이너스를 하게 되면 안 좋아지는 거임?!?

그래서 멘붕와서 못 풀다가 구글링했다..

구글링

여기가 나랑 푸는 방법도 비슷하고 깔끔해서 도움이 됐다

보니까 return을 하지말고, 어디까지 봤는지 index랑 그 동안 value를 들고다니면서
index가 끝을 보면 value를 result랑 비교해서 업데이트 해준다
(아니 이렇게 쉬운걸 모르다니..)

근데 저 코드는 index가 오른쪽 숫자를 가리킨다고 해야할까..
예를 들어 a+b+c 수식을 볼 때
index - 2 가 a를, index 가 b를, index + 2가 c를 바라보게 짜여있어서
dfs(0, 0) 로 호출하고, index - 1 이 0보다 같거나 작으면 op를 +로 처리하는 등
내 기준으론 이해하기 쉽지 않았어서

index 가 a를 index + 2가 b를 보게 변경했다 (아래 코드 참조)
이러면 dfs(0, s[0])로 호출하고, 따로 + op 처리를 안 해줘도 됌!

주의해야 할 점

파이썬으로 코드를 제출하니까 80% 쯤에 런타임에러(TypeError) 가 떴다
뭐 타입에러는 내가 알기론 str 이랑 int를 대소비교한다거나 그럴 때 발생하는거니까
내 코드에서 그런 곳이 어디있을까~ 찾으니까

if index == n - 1:
        result = max(result, value);
        return

이 부분에서 에러가 발생하겠구나!
언제는 value가 str일까~ 생각했더니

맨 처음 dfs(0, s[0])으로 호출시 str으로 넘겨줘서
n이 1일 경우 바로 result랑 비교해버려서 그랬던 것!
dfs(0, int(s[0]))로 변경해줬다

코드

import sys

n = int(input())
s = input()
result = -1 * sys.maxsize

def myOperator(num1, oper, num2):
    if oper == '+':
        return num1 + num2
    if oper == '-':
        return num1 - num2
    if oper == '*':
        return num1 * num2

def dfs(index, value):
    global result

    if index == n - 1:
        result = max(result, value);
        return

    if index + 2 < n:
        dfs(index + 2, myOperator(value, s[index + 1], int(s[index + 2])))

    if index + 4 < n:
        dfs(index + 4, myOperator(value, s[index + 1], myOperator(int(s[index + 2]), s[index + 3], int(s[index + 4]))))

dfs(0, int(s[0]))
print(result)