알고리즘 풀이/백준(Boj)
백준 BOJ(16637번) 괄호 추가하기
100win10
2020. 3. 21. 17:06
문제 : https://www.acmicpc.net/problem/16637
16637번: 괄호 추가하기
첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.
www.acmicpc.net
풀이 :
홀수인 부분은 모두 부호이니 +면 1 *면 2 -면 3으로 바꿔서 풀어주었다.
비트 마스킹을 통해 첫 번째 예제를 예로 들면
index가 1 , 3, 5, 7, 13, 15, 17, 35, 37, 57, 135, 137, ,157, 357, 1357 인 부분의 괄호들을 처리하며 ( 1 << m )
이때 괄호가 겹칠 수 있는 13 17 등의 부분들은 바로 넘어가게 된다.
코드 ( C++ )
