[BOJ] 백준 16637번 - 괄호 추가하기(with Java)

알고리즘

브루트포스로 접근해서 풀어보다가 못풀고 시간만 보낼것 같아서 결국 구글링했다.

문제 분류에는 브루트포스만 적혀있지만 DFS + 재귀 조합을 통해서도 풀 수 있었다.

 

'괄호를 채워넣지 않는 경우(1)'와 '괄호를 채워넣는 경우(2)' 2가지로 나눠볼 수 있겠다.

(1)의 경우에는 total로 넘겨준 값을 유지하면서 오른쪽의 숫자들을 계속 연산해준다.

(2)의 경우에는 total의 바로 뒤에 오는 숫자들에 대해서 먼저 연산해주고, total을 유지한채 다음 DFS를 수행한다.

 

만약에 주어진 연산자들을 모두 사용하면 total과 max값을 갱신시켜준다.

이후에 다음 DFS를 수행하지 않고 함수를 빠져나오면 된다.

예시

예제로 주어진 입력1의 '3+8*7-9*2'를 살펴보자.

괄호를 추가하지 않고 이 문제에서 주어진 방식으로 계산하면 136이 도출된다.

맨 앞의 3에 대해서는 괄호를 씌우지 않고 앞에서부터 계산하는것과 같으므로 8부터 보면 된다.

 

괄호를 씌우는 경우는 총 3가지이다.

(1) '3+(8*7)-9*2' -> 3 + 56 - 9 * 2

(2) '3+8*(7-9)*2' -> 11 * (-2) * 2

(3) '3+8*7-(9*2)'

 

그렇다면 이 경우의 수를 모두 고려해줘야할까? 그렇지 않다.

맨 처음에 괄호를 추가하는 것을 고려해주는 경우는 (1)뿐이다.

(1)은 3을 total로 가지고 가고, 바로 뒤 수식인 8*7에 괄호를 추가하는 경우이다.

(2)는 3+8을 더해서 11을 total로 가지고 가고, 바로 뒤 수식인 7-9에 괄호룰 추가하는 경우이다.

 

(3)은 괄호를 씌우지 않고 앞에서부터 쭉 계산해주는 것과 동일하다.

풀이의 핵심은 맨 앞의 수 뒤부터만 괄호를 칠지 말지 고려해주는 것이다.

소스코드

문제링크

16637번: 괄호 추가하기