백준 16637 파이썬 | 괄호 추가하기 | 삼성 A형 기출 문제 | 코딩 테스트

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

---

 

처음에는 이 문제를 이해하는데 조금 시간이 걸렸다.

그 이유는 바로 문제를 제대로 읽지 않았기 때문이다..ㅋㅋ

문제를 제대로 읽으면 헤맬 일이 없다. 

나는 헤맸고, 나와 비슷하게 헤맨 사람이 있어서 한번 더 문제에서 중요한 부분을 강조하고자 한다.

 

"연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다."

"예를 들어, 3+8x7-9x2 = 136이다."    →  3 + 8 = 11 x 7 = 77 - 9 = 68 x 2 = 136

 

친절하게 예까지 들어줬으나, 이걸 생각하지 않고 그저 괄호를 어디다 넣어야할지, 예제 입력과  출력을 매칭시키려니 당연히 안되는 것이었다.

 

추가 조건

괄호의 개수 제한은 없으나, 괄호 중첩은 안된다.

 

괄호 중첩이 안된다는 조건으로 인해 경우의 수가  상당히 줄어든다.

그렇다면 먼저 예시의 수식을 통해 괄호가 들어갈 수 있는 경우의 수를 판단해보자.

괄호를 넣을 연산자의 순서를 매기면 다음과 같다. 

 

예를 들어, (2)과 (4)의 연산자를 기준으로 괄호를 넣는다면 아래와 같이 된다.

 

하지만, 아래와 같이 두번째, 세번째 연산자에 괄호를 넣는 경우는 괄호가 중복되므로 불가능한 것이다.

 

연속된 연산자에는 괄호를 넣지 못하므로, 위의 케이스에서는 괄호를 가질 수 있는 경우의 수는 아래와 같다.

1. (2) → 3+(8x7)-9x2 = (3+56-9)x2 = 100

2. (3) → 3+8x(7-9)x2 = 11x(-2)x2 = -44

3. (4) → 3+8x7-(9x2) = 77-18 = 59

4. (2), (4) → 3+(8x7)-(9x2) = 3+56-18 = 41

5. 괄호 x → 136

 

즉, 이 경우에는 최대값은 136이며, 이에 해당하는 케이스는 괄호가 아예 없는 경우에 해당한다.

 

모든 경우를 계산해보지 않으면 최대값을 가지는 경우를 미리 알기는 어려울 것이라 판단되므로, 

연산자 別 괄호 사용 여부를 모두 체크하여 계산하는 방식으로 진행한다.

+ (1)에 괄호를 넣는 것은 안넣는 것과 동일하므로 (2)~(4)에 대해서만 괄호 여부를 판단하면 된다.

 

코드의 핵심은 DFS (Depth-First Search) 이며, 참고할 블로그 링크 하나 남겨놓겠다.

https://cobi-98.tistory.com/30

 

#### string 인식 연산자 함수
def calculate(a, b, op):
    if op == '+':
        return a + b
    elif op == '-':
        return a - b
    elif op == '*':
        return a * b
#-------------------------------------------------
#### dfs 함수
def dfs(index, current_value):
    global max_value

    if index == len(expression):
        max_value = max(max_value, current_value)
        return

    next_value = calculate(current_value, int(expression[index+1]), expression[index])
    dfs(index + 2, next_value)

    if index + 4 <= len(expression):
        bracket_value = calculate(int(expression[index+1]), int(expression[index+3]), expression[index+2])
        next_value = calculate(current_value, bracket_value, expression[index])
        dfs(index + 4, next_value)
#-------------------------------------------------
#### 입력 및 초기화 단계
N = int(input())  # 수식의 길이
expression = input().strip()
max_value = -2**31
#-------------------------------------------------
#### 함수 실행
dfs(1, int(expression[0]))
#-------------------------------------------------
#### 결과 출력
print(max_value)

 

코드는 위와 같다.

필요한 함수들을 먼저 정의한 다음, 초기화 및 입력 변수를 받는다.

그 다음은 dfs(1, int(expression[0])을 입력하면 수식 내의 가능한 모든 괄호의 경우의 수로부터 나오는 결과 中 최대값을 산출해준다.

 

계산의 흐름은 아래와 같다.

 

dfs 계산 결과

 

 

위와 같은 방식으로 순차적으로 계산해 결과값을 얻으며, 이전의 결과값보다 더 큰 결과값이 있으면 갱신하고 그렇지 않으면 이전의 결과값이 유지되는 형식으로 하여 최종적으로 가장 큰 결과값을 산출할 수 있는 것이다.

이 문제에서는 어차피 모든 경우의 수를 다 계산해봐야하는 것이니, 순서는 중요하지 않다.

(순서는 아래의 1->3->5->7->9부터 한다음, 위로 한칸씩 올라온다고 보면 된다.)

---

개발자가 아니라 과학계산용으로만 코딩을 해왔던 터라, 알고리즘 공부는 처음이라 DFS도 처음 듣고, 이해하는데에도 시간이 어느정도는 걸렸던 것 같다. (마치 수능 공부하던 학생이, 수학 경시대회를 준비하는 느낌.)

이런식으로 꾸준히 공부해보고 내가 이해한 바를 기록으로 남기다보면 실력이 쌓이지 않을까 생각하며, 오늘은 이만 마치겠다.

코테 공부하는 모든 분들 화이팅!

 

(혹시 틀린게 있다면 피드백 주시면 감사하겠습니다!)