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

https://www.acmicpc.net/problem/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))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

 

[Input]

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

 

[Output]

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -231보다 크다.

---

[ Solution ]

최소값을 구하기 위해??

당연히 모든 경우의 수를 다 따져보아야 할 것입니다.

 

괄호는 없어도 되고, 많아도 됩니다.

그렇다면, 괄호가 생성될 수 있는 모든 경우의 수를 골라야지요.

(1) 연산자는 홀수 인덱스에 존재합니다.

(2) 연속된 홀수 값은 동시에 괄호가 존재할 수 없습니다.

 

그렇게 우선 계산할 연산자를 중복 없는 조합(purmute() 함수)을 통해 구해냅니다.

 

다음, 괄호 생성이 가능한 모든 경우의 수를 전부 계산해줍니다.

newLine_fromIndex() 함수를 통해 연산자 하나를 우선 계산하고 새로운 식을 반환해주었구요.

calculation() 함수를 통해 전체 식을 계산해주는 함수를 생성했습니다.

 

위 두 함수를 이용해서 생성 가능한 모든 괄호에 대해 결과값을 계산해줬습니다.

 

def solution(number, line):
    # 전체 계산
    def calculation(lines): # 연산 함수
        # input : 계산식 (string)
        # output : 결과값 (int)
        
        if lines[0] == "-":   # 계산식 처음이 음수라면
            lines = "0"+lines # 맨 앞에 0 추가
        
        nums = "" # 두자리 이상 숫자 계산 위해
        line = [] # 계산할 식 담을 리스트 선언
        for i in lines:
            if i.isdigit() == False: #문자일 때
                if nums != "": # 숫자가 담긴 경우
                    line.append( nums ) #리스트에 숫자 추가
                line.append( i ) #리스트에 연산자 추가
                nums = "" #숫자 초기화
            else: nums += i #연산자 추가
        line.append(nums) #마지막 숫자 추가
        
        result = int(line[0]) # 계산값 처음에 첫번째 숫자 선언
        for index, c in enumerate(line[1:]):
            if c.isdigit(): # 숫자일 경우
                op = line[index] 
                if op == "+": result += int(c) #덧셈 계산
                elif op == "-":  # 뺄셈 계산
                    if line[index-1] == "*": # 만약 곱셈과 연속일 경우
                        result *= int(c) * -1 # 음수로 곱셈 연산
                    else:
                        result -= int(c) # 뺄셈 연산
                    
                else : result *= int(c) # 곰셈 연산
        
        return result
    
    # 연산자 인덱스를 통해 새로운 계산식 생성
    def newLine_fromIndex(index, line):
        # input
        #   - index : 연산자 위치 (int)
        #   - line : 계산식 (string)
        # output : 연산자 계산한 새로운 계산식 (string) 
        
        a, b, result = int(line[index-1]), int(line[index+1]), 0
        
        # 연산자 따라서 계산
        if line[index] == "+": result = a + b
        elif line[index] == "-": result = a - b
        else : result  = a * b

        if result < 0: # 계산값이 음수일 경우
            if line[index-2] == "+": # 이전 연산자가 덧셈일 때 -> 덧셈 제거
                new_line = line[:index-2] + str(result) + line[index+2:]
            elif line[index-2] == "-": # 이전 연산자가 뺄셈일 때 -> 덧셈으로 변환
                new_line = line[:index-2] + "+" + str(result*-1) + line[index+2:]
            else: # 이전 연산자가 곱셈일 때 -> 그대로
                new_line = line[:index-1] + str(result) + line[index+2:]
        else:
            new_line = line[:index-1] + str(result) + line[index+2:]

        # 결과 계산식 맨 앞이 음수일 경우 -> 맨 앞에 0 붙여줌
        if new_line[0] == "-" : new_line = "0"+new_line

        return new_line

    # 조합 생성
    def permute(array, r): # 중복 제거 조합 계산
        # input
        #   - array : 숫자 리스트 (list)
        #   - r : 조합 개수 (int)
        # output : 조합 tuple 리스트 (list)

        for i in range(len(array)):
            if r == 1: # 종료 조건
                yield [array[i]]
            else:
                for next in permute(array[i+1:], r-1):
                    yield [array[i]] + next

    # 우선 계산할 연산자 인덱스 리스트 반환
    def calc_position(count, length): 
        # input
        #   - count : 몇 개의 괄호를 칠 지 (int)
        #   - length : 총 연산식 길이 (int)
        # output : 중복 없고, 연속되지 않은 연산자 위치 리스트 (list)

        result = []
        # 연산자 위치 인덱스 리스트
        calc_list = [ x for x in range(length)  if x%2 ==1 ]
        # 중복 제거한 조합 계산
        _list = [ x for x in permute(calc_list, count) ]

        for nums in _list:
            isTrue = True
            for num in nums: # 조합이 연속으로 존재하는 경우 -> 제거
                if num-2 in nums or num+2 in nums: 
                    isTrue = False
                    break
            # 연속으로 존재하지 않으면 -> 결과 조합에 추가
            if isTrue: result.append( nums )

        return result
                
        
    max_output = -1 * (2 ** 31) # 최대 결과값 저장 변수 (최소값으로 초기화)

    max_calc = number // 2
    # 괄호 최대 개수
    max_bracket = max_calc // 2 if max_calc % 2 == 0 else max_calc //2 + 1

    num = 1 # 괄호 개수
    while num < max_bracket+1 : #괄호 개수를 최대값까지 반복
        for position in calc_position(num, number): # 조합 개수 전달
            # 새로운 계산식 복사
            newline = "".join([ x for x in line ])
            for p in sorted(position, reverse=True):
                # 연산자 괄호친 것 우선 계산 -> 새로운 계산식 반환
                newline = newLine_fromIndex(p, newline)

            value = calculation( newline) # 결과 계산
            # 계산식 초기화
            newline =  "".join([ x for x in line ])
            if max_output < value: # 최대값보다 결과값이 크면
                max_output = value #최대값 = 결과값
    
        num += 1
    value = calculation( line) # 괄호 아무것도 치지 않고 계산한 경우
    if max_output < value:  max_output = value

    return max_output


if __name__ == "__main__":
    number = int(input())
    line =   input()
    
    print( solution(number, line) )