[Gold III] 괄호 추가하기 - 16637
성능 요약
메모리: 11640 KB, 시간: 76 ms
분류
브루트포스 알고리즘, 구현
제출 일자
2023년 10월 17일 14:31:24
문제
문제 설명
길이가 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은 홀수이다.
출력
첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -2보다 크다.
문제 요약
- 수식의 홀수번째 인덱스에는 연산자가 온다
- 수식에 추가하는 괄호는 연산자가 하나만 들어있어야 한다. 또한 중첩된 괄호는 사용할 수 없다.
- 연산의 기본 순서는 왼쪽부터
접근 아이디어
하나의 연산자에 괄호를 적용한다면 그 다음 연산자는 괄호를 적용할 수 없다. 중첩된 괄호는 사용할 수 없기 때문이다. 여기서 시작해서 이전 연산자의 괄호 적용 여부를 체크한 뒤, 지금 연산자에 괄호를 적용할 때, 적용하지 않을 때를 나눠서 계산하는 방식으로 구현했다.
또한 각 분기 별로 계산결과가 달라지기 때문에 deque에 현재 계산 상태를 복사해서 다르게 분기될 수 있도록 했다.
작성 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static int N;
static char[] expression;
static int max = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
expression = br.readLine().toCharArray();
Deque<Integer> num = new ArrayDeque<>();
Deque<Character> oper = new ArrayDeque<>();
num.push(expression[0] - '0');
dfs(1, false, num, oper);
System.out.println(max);
}
static void dfs(int idx, boolean flag, Deque<Integer> num, Deque<Character> oper) {
if (idx == N) {
while (!oper.isEmpty()) {
int first = num.removeLast();
char o = oper.removeLast();
int second = num.removeLast();
num.add(calc(first, second, o));
}
int res = num.pop();
if (res > max) {
max = res;
}
return;
}
Deque<Integer> tnum = new ArrayDeque(num);
Deque<Character> toper = new ArrayDeque(oper);
if (flag) { // 이전 연산자에서 괄호를 적용함
// 이번 연산자에서는 괄호 적용할 수 없음
// 그럼 나랑 내 다음 연산자 넣고 다음으로 넘어가기
tnum.push(expression[idx + 1] - '0');
toper.push(expression[idx]);
dfs(idx + 2, false, tnum, toper);
} else {
// 괄호 적용 o
int t = tnum.pop();
tnum.push(calc(t, expression[idx + 1] - '0', expression[idx]));
dfs(idx + 2, true, tnum, toper);
// 괄호 적용 x
num.push(expression[idx + 1] - '0');
oper.push(expression[idx]);
dfs(idx + 2, false, num, oper);
}
}
static int calc(int a, int b, char c) {
switch (c) {
case ('+'):
return a + b;
case ('-'):
return a - b;
default:
return a * b;
}
}
}
'알고리즘' 카테고리의 다른 글
[BOJ7662/Java] 이중 우선순위 큐 (0) | 2023.12.15 |
---|---|
[BOJ2473/JAVA] 세 용액 (0) | 2023.12.14 |
[BOJ1963/Java] 소수 경로 (0) | 2023.10.03 |
[BOJ1339/Java] 단어 수학 (0) | 2023.09.27 |
[BOJ11501/Java] 주식 (0) | 2023.09.26 |