코드와이
[BAEKJOON] 16637. 괄호 추가하기 본문
문제링크
https://www.acmicpc.net/problem/16637
ans의 초기값을 0으로 설정하면 14퍼에서 틀립니다!!
최솟값 설정을 적절하게 해주어야 통과할 수 있습니다.
package acmicpc.Gold3;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class 괄호_추가하기 {
static int ans;
static List<Integer> num;
static List<Character> op;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
char[] input = br.readLine().toCharArray();
num = new ArrayList<>();
op = new ArrayList<>();
for(char c : input) {
if(c <= '9' && c >= '0') num.add(c - '0');
else op.add(c);
}
ans = -987654321;
dfs(0, num.get(0));
System.out.println(ans);
}
public static void dfs(int idx, int sum) {
if(idx >= op.size()) {
ans = Math.max(ans, sum);
return;
}
// 괄호 없이
dfs(idx + 1, calc(sum, num.get(idx + 1), op.get(idx)));
// 괄호 있이
// 연산자가 최소 하나 더 있어야한다.
if(idx + 1 < op.size()) {
int tmp = calc(num.get(idx + 1), num.get(idx + 2), op.get(idx + 1));
dfs(idx + 2, calc(sum, tmp, op.get(idx)));
}
}
public static int calc(int n, int x, char op) {
if(op == '+') {
return n + x;
} else if(op == '-') {
return n - x;
} else if(op == '*'){
return n * x;
}
return 1;
}
}
'acmicpc' 카테고리의 다른 글
[BAEKJOON] 2533.사회망 서비스 (0) | 2021.12.11 |
---|---|
[BAEKJOON] 11779. 최소비용구하기2 (0) | 2021.12.10 |
[BAEKJOON] 11437. LCA (0) | 2021.12.01 |
[BAEKJOON] 2437. 저울 (0) | 2021.11.23 |
[BAEKJOON] 1300. K번째 수 (0) | 2021.11.06 |