[BOJ] 16337 괄호 추가하기

16637번: 괄호 추가하기

문제

길이가 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은 홀수이다.

9
3+8*7-9*2

출력

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

136

---

얼마 전에 삼성 S/W 광탈한 기념으로 삼성 기출문제를 풀어봤다.

 

처음 봤을 때는 재귀함수를 사용해서 괄호의 위치를 잡아두고 계산하는 방법이 떠올랐다.

그런데 구현하는게 쉽지 않았다.

계속 계산이 이상한 값으로 나와서 이게 아닌가 싶었다.

 

그다음으로 생각한 건 그다음 연산자를 미리 계산하고 이번 연산을 하는 방법이다.

이 방법은 충분히 가능할 것 같았지만 시작과 끝에서 예외처리가 필요해 보였다.

일단 구현한 후에 예제를 돌려보니 값이 잘 나오는 듯싶었다.

 

14%쯤에서 틀렸습니다가 떴다.

정답이 음수인 경우를 생각하지 않아서 생긴 문제였다.

따라서 limits.h의 INT_MIN을 사용해서 answer 변수를 초기화해 해결했다.

 

정확히는 모르겠지만 채점이 거의 끝나기 직전에도 틀렸습니다가 떴다.

백준 사이트에서 테스트 케이스 큰 것부터 돌린다고 알고 있어서

N이 1인 경우를 입력해봤다.

당연히 안되더라. 이 경우까지 예외 처리하고 나니 맞았습니다를 볼 수 있었다. 

 

 

 

후기)

뭐든지 디테일을 살리는 게 중요하다.

문제를 처음 봤을 때는 별로 안 어려워 보였는데 쉽게 풀지는 못 했다.

이런 DFS 문제는 자신 있었는데 이젠 아닌 거 같다.