[백준 - Python] 16637 - 괄호 추가하기

0.  문제 링크

 

 

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

16637번: 괄호 추가하기

---

1.  풀이 방법

 

 

**코드 길이 주의

 

해당 알고리즘은 브루트포스로 풀었다.

최대 길이는 19이고, 따라서 연산자는 최대 9개가 가능하다.

중첩된 괄호는 불가능하므로, 연산자는 최대 5개까지 선택이 가능하다.

물론 연산자 5개는 단 한 번만 가능하다.

연산자 4개를 뽑는 경우도 의외로 적다.

중첩된 괄호라는 조건을 제외하면 최대 9C5 + 9C4 + 9C3 + 9C2 + 9C1 + 9C0 = 126 + 126 + 84 + 36 + 9 + 1 = 382이다.

따라서 구현을 잘하면 빠르게 문제를 풀 수 있다.

 

---

2.  코드

 

 

import sys
from collections import deque
input = sys.stdin.readline


def calculate(dq : deque()):
    while len(dq) > 1:
        dq.appendleft(str(eval(dq.popleft() + dq.popleft() + dq.popleft())))
    return dq.popleft()
        

def choice(cnt):
    global maxNum
    for a in range(1, n, 2):
        num1 = str(eval(''.join(maps[a - 1 : a +  2])))
        if cnt == 1:
            maxNum = max(maxNum, int(calculate(deque(maps[:a - 1] + [num1] + maps[a + 2:]))))
        if cnt >= 2:
            for b in range(a + 4, n, 2):
                num2 = str(eval(''.join(maps[b - 1 : b + 2])))
                if cnt == 2:
                    maxNum = max(maxNum, int(calculate(deque(
                        maps[: a - 1] + [num1] + 
                        maps[a + 2 : b - 1] + [num2] + 
                        maps[b + 2 :]
                        ))))
                if cnt >= 3:
                    for c in range(b + 4, n , 2):
                        num3 = str(eval(''.join(maps[c - 1 : c + 2])))
                        if cnt == 3:
                            maxNum = max(maxNum, int(calculate(deque(
                                maps[: a - 1] + [num1] + 
                                maps[a + 2 : b - 1] + [num2] + 
                                maps[b + 2 : c - 1] + [num3] + 
                                maps[c + 2 :]
                                ))))
                        if cnt >= 4:
                            for d in range(c + 4, n, 2):
                                num4 = str(eval(''.join(maps[d - 1 : d + 2])))
                                if cnt == 4:
                                    maxNum = max(maxNum, int(calculate(deque(
                                        maps[: a - 1] + [num1] + 
                                        maps[a + 2 : b - 1] + [num2] + 
                                        maps[b + 2 : c - 1] + [num3] + 
                                        maps[c + 2 : d - 1] + [num4] + maps[d + 2 :]))))
                                if cnt >= 5:
                                    for e in range(d + 4, n, 2):
                                        num5 = str(eval(''.join(maps[e - 1 : e + 2])))
                                        if cnt == 5:
                                            maxNum = max(maxNum, int(calculate(deque(
                                                maps[: a - 1] + [num1] + 
                                                maps[a + 2 : b - 1] + [num2] + 
                                                maps[b + 2 : c - 1] + [num3] + 
                                                maps[c + 2 : d - 1] + [num4] + 
                                                maps[d + 2 : e - 1] + [num5] + 
                                                maps[e + 2 : ]
                                                ))))


if __name__ == "__main__":
    n = int(input())
    maps = list(input().strip())
    maxNum = int(calculate(deque(maps)))
    
    for cnt in range(1, n // 4 + 1):
        choice(cnt)
    
    print(maxNum)

---

3.  마무리