https://www.acmicpc.net/problem/16637
이 문제 생각보다 굉장히 어려웠다. ㄷㄷㄷ
머리야 돌아가!!!
순서
0. 저장할 때 숫자와 연산자를 따로 저장함
- dfs로 완전 탐색을 돌건데 괄호를 치거나 안치거나 둘 중 하나잖음 그래서 따로 재귀 타야함
- index로 훑을건 연산자!
- 연산자 인덱스 0일 때 num 0,1과 함께 계산, 1일 때 num 1,2 계산.. 등등
- 첫 번째 숫자는 result에 미리 넣어놓는다. 그리고 +,-,*에 따라 계산해주는 메소드 따로 만듦
1. 괄호 안칠 때
- 현재 index에 대한 연산자로 계산해줌.
- result와 i+1번째 num을 i번째 연산자로 계산!
2. 괄호 칠 때
- 괄호는 무조건 연산자 index 뒤에 있는곳에 칠거임
- 그래서 i번째 말고 i+1번째 연산자와 i+1번째 num, i+2번째 num을 계산한 결과를 따로 저장 (= suf)
- 그 전까지의 결과인 result와 뒤에 괄호쳐서 계산한 값인 suf를 i번째 연산자로 계산
- dfs로 넘길 때에는 i+1번째 연산자까지 계산이 완료된 후 이므로 i+2를 보낸다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int N;
static ArrayList<Integer> num = new ArrayList<>();
static ArrayList<Character> math = new ArrayList<>();
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
String line = br.readLine();
for(int i=0; i<N; i++) {
if(i % 2 == 0) num.add(line.charAt(i) - '0');
else math.add(line.charAt(i));
}
dfs(0, num.get(0));
System.out.println(answer);
}
static int answer = Integer.MIN_VALUE;
private static void dfs(int i, int result) {
if(i >= math.size()) {
answer = Math.max(answer, result);
return;
}
// 괄호 X
dfs(i+1, calc(math.get(i), result, num.get(i+1)));
// 괄호 O
if(i+1 < math.size()) {
// 뒤 먼저 계산하고 앞에까지 계산한 result랑 다시 계산한ㅁ
int suf = calc(math.get(i+1), num.get(i+1), num.get(i+2));
dfs(i+2, calc(math.get(i), result, suf));
}
}
private static int calc(char m, int x1, int x2) {
if(m=='+') return x1+x2;
else if(m=='-') return x1-x2;
else return x1*x2;
}
}
댕어러워
'알고리즘 > 백준' 카테고리의 다른 글
[BaekJoon] 백준 17136번 _ 색종이 붙이기 for JAVA (0) | 2022.11.20 |
---|---|
[BaekJoon] 백준 17825번 _ 주사위 윷놀이 for JAVA (0) | 2022.11.20 |
[BaekJoon] 백준 19236번 _ 청소년 상어 for JAVA (0) | 2022.11.13 |
[BaekJoon] 백준 3190번 _ 뱀 for JAVA (0) | 2022.11.06 |
[BaekJoon] 백준 15644번 _ 구슬 탈출 3 for JAVA (0) | 2022.10.30 |