[백준/16637/파이썬] 괄호 추가하기

https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

Problem

• 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다.
• 수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

조건

•  연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.
• 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다.
• 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.
• 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다

SOL

정말 어려워서, 결국 블로그들을 찾아본 문제.

 

생각노트

예제를 몇개 직접 해보고 나서, 혹시 규칙이 있나 살펴보았다. 

 

1.Greedy하게 풀 수 있지 않을까?

 +, -, * 일때, 뒤에 각각 무엇이 오냐에 따라서 뭘 먼저해줄지 우선순위를 정해주면 그 순서를 따라가지 않을까 생각을 해보았다.

 

1. 연산자가 2개 이상 있을 때, +가오고, *가 오는경우, 어떤걸 먼저 해주는게 이득일까? 
   • (9+5)*9=14*9, 9+(5*9)=45+9
   • (10+3)*100 =1300, 10+(3*100)=310
   • (10+0)*500=10*500, 10+0= 10
   • 대체적으로는 더하기가 먼저하는게 이득이다. 하지만, 확실하지는 않다.
2.  +가 오고, -가 오는 경우, 어떤걸 먼저해주는게 이득일까?
   • +와 -는 교환법칙이 성립하기 때문에, 누구를 먼저하든 상관이 없다.
   • 음수일 때도 그럴까? 
3. 마찬가지로, +가오고 ,+가 오는경우에는 뭘 먼저 하든지 상관이 없을것 같다. 

하지만, 연산자가 2개 이상올때로 확장시키려고 해보니까, 위의 규칙은 깨져버렸다. 어쩌면 당연한 거 일수도 있다. 애초에, 가정을 연산자 2개만 보아줬으니까

 

결국, 모든 경우를 다 탐색해주는 풀이방법으로 가야겠다.

 

완전탐색

항상, 완전탐색을 할때는, TL이 걸리는지 , 안걸리는지 생각을 한번쯤 하고 돌려야한다. 연산자가 최대 9개가 올 수 있으니까,

괄호가 1개인 경우 = 연산자 1개를 선택해서 양쪽 수를 묶어준다.

괄호가 2개인 경우 = 연산자 2개를 선택해서, 양쪽 수를 묶어준다. ( 이때, 첫번째 선택한 수 바로 옆의 연산자는 선택 못함) 예를들어, 8+4+3*10+3-4 에서, (8+4)+3)*10)처럼, 연속해서 연산자를 선택하지 못한다는 이야기임! 

괄호가 3개인 경우 = 연산자를 3개 선택해서, 각각 연산자의 양쪽 수를 묶어준다. 마찬가지로, 연속해서 연산자를 선택하지 못한다.

그렇다면, 러프하게, 경우의 수가 9C1+9C2+9C3....9C5 까지 라고 생각할 수 있다.(물론 저 경우의수보다 작다. 연속해서 연산자를 선택하지 못하기 때문에) 하지만, 이로써, 완전탐색이 충분히 가능할거 같다. 

 

구현을 어떤식으로 할 수 있을까 ?조합을 이용하려니까, 연속해서 연산자를 선택하지 못한다는 점이 불-편하다.

결국, 재귀적으로 구현하고, idx 관계를 생각해주면서 구현할 수 밖에 없을거 같다.

이때 idx는 숫자만 가리키게 구현을 할거다.

 

괄호를 집어넣은 식을 만들어 준다. 

• 괄호를 집어 넣은 식,괄호를 집어 넣지 않은 식 중에 큰 값을 return 해주면 된다. 
• 그러면, 계산하는 부분과, 재귀를 끝내는 부분을 정해줘야한다.

식이 완성되려면, idx가 2가지에서 분기점이 발생하게 된다.

 

탈출지점

 

idx가 N-1일때, 

- 더 이상 괄호를 만들어 줄 수 없으므로, 괄호가 없는 식으로 생각하고, 마지막 수를 더해준다!

idx가 N-3일 때,

- 괄호를 만들어주고 끝낼 수도 있고, 그 뒤에 괄호가 없는식으로 끝까지 밀고 나갈 수 있음.

Body

• 괄호가 없는 식
  • 기존 식 + [f[i]+f[i+1]] ( 기존식 + 피연산자 +연산자)
• 괄호가 있는 식
  • 기존식 + [f[i]+f[i+1]+f[i+2]를 계산한 값 , f[i+3]]
• return max (재귀함수(idx+2,괄호가 없는식),재귀함수(idx+4,괄호가 있는식))

import sys
input= sys.stdin.readline
sys.setrecursionlimit(10**6)
# 바로 옆에 있는 연산자 빼고 선택가능

N=int(input().rstrip())
f=[int(x) if x !="+" and x !="*" and x !="-" else x for x in input().strip()]

def cal_queue(queue):
    result=queue[0]
    for i in range(0,len(queue)-2,2):
        post=queue[i+2]
        result=cal_nums(result,post,queue[i+1])
    return result

def cal_nums(pre:int,post:int,op:str) ->int:
    if op=="+":
        return pre+post
    if op=="-":
        return pre-post
    if op=="*":
        return pre*post

def insert_bracket(idx,q):
    if idx==N-1:
        no_br=q+[f[idx]]
        return cal_queue(no_br)
    if idx==N-3:
        no_br=q+[f[idx],f[idx+1]]
        tmp=cal_nums(f[idx],f[idx+2],f[idx+1])
        br=q+[tmp]
        return max(insert_bracket(idx+2,no_br),cal_queue(br))
    no_br=q+[f[idx],f[idx+1]]
    tmp=cal_nums(f[idx],f[idx+2],f[idx+1])
    br=q+[tmp,f[idx+3]]
    return max(insert_bracket(idx+2,no_br),insert_bracket(idx+4,br))

print(insert_bracket(0,[]))