알고리즘/백준

[BaekJoon] 백준 16637번 _ 괄호 추가하기 for JAVA

정석이 2022. 11. 13. 23:14

 

https://www.acmicpc.net/problem/16637

 

16637번: 괄호 추가하기

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가

www.acmicpc.net

 

 

문제

 

 


 

 

이 문제 생각보다 굉장히 어려웠다. ㄷㄷㄷ

 

머리야 돌아가!!!

 

 

순서

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;
	}
}

 

 

 

성능

 

 

댕어러워