[백준/JAVA] 16637번: 괄호 추가하기

📖 문제

16637번: 괄호 추가하기

 

💡  풀이 방식

• DFS + 백트래킹

1. 이전 연산 결과 순차적으로 계산

2. 이전 연산 결과 오른쪽의 2개의 값을 괄호로 처리해 계산하고, 이전 연산 결과와 합침

 

DFS 통해 맨 뒤에서부터 괄호를 묶을 수 있는 경우 묶으면서 연속적으로 계산

연산자 인덱스 기준 접근

 

- 숫자 리스트와 연산자 리스트를 따로 두어야 한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int ans = Integer.MIN_VALUE;
    static List<Character> ops = new LinkedList<>();    // 연산자 리스트
    static List<Integer> nums = new LinkedList<>();        // 숫자 리스트
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        String input = br.readLine();
        
        for(int i = 0 ; i < N ; i++) {
            char c = input.charAt(i);
            
            if(c == '+' || c == '-' || c == '*') {
                ops.add(c);
                continue;
            }
            
            nums.add(c - '0');
        }
        
        dfs(nums.get(0), 0);
        System.out.println(ans);
    }
    
    // 연산 메소드
    private static int calc(char op, int n1, int n2) {
        if(op == '+')        return n1 + n2;
        else if(op == '-')    return n1 - n2;
        else if(op == '*')    return n1 * n2;
            
        return -1;
    }
    
    // 괄호 묶을지 풀지 판단하는 메소드 (DFS + 백트래킹)
    private static void dfs(int result, int depth) {
        // 주어진 연산자 갯수 초과하면 정답 출력
        if(depth >= ops.size()) {
            ans = Math.max(ans, result);
            return;
        }
        
        // 1) 괄호 안 치고 넘기기
        int res1 = calc(ops.get(depth), result, nums.get(depth + 1));
        dfs(res1, depth + 1);
        
        // 2) 괄호 치고 넘기기 (맨 뒤쪽에서부터)
        if(depth + 1 < ops.size()) {
            // result의 오른쪽에 있는 값 연산
            int res2 = calc(ops.get(depth + 1), nums.get(depth + 1), nums.get(depth + 2));
            
            // 현재 result와 방금 구한 괄호 값을 연산한 결과와 괄호 오른쪽에 존재하는 연산자의 인덱스 넘김
            dfs(calc(ops.get(depth), result, res2), depth + 2);
        }
    }
}
 

 

 

➕ 다른 풀이 방식

[백준 16637] 괄호추가하기 -JAVA //le_effort

[JAVA]백준 16637번: 괄호 추가하기

 

 

- 좋은 설명과 그림...💕

[JAVA] 괄호 추가하기 (백준 16637)

---

💦 어려웠던 점

직접 리스트에 괄호 추가해보고 이렇게 하려고 했는데 구현을 잘 하지 못해서 고민하다가 다른 분 풀이를 보고 제출했다.

 

괄호 추가하고 제거하는 부분에서 DFS+백트래킹 쓰는 문제를 전혀 혼자서 못 풀고 있다.

복습이랑 훈련 좀 해야겠다.ㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V	240505

 

 

(+ 240505 2회독)

개선된 점

- 백트래킹으로 괄호 칠지 말지의 아이디어를 생각해 내긴 했다.

 

놓친 점

예를 들어 a + b - c의 경우

1) 괄호를 안 치고 넘어가는 경우 : a + b하고 넘기기

2) 괄호를 치고 넘어가는 경우 : a + (b - c) 하고 ㄴ머기기

이렇게 괄호를 치느냐에 따라 2가지 경우로 나뉜다.

 

이 경우를 어떻게 처리해야할지 손대지 못 했다..

---

(참고)

✔ 풀이 참고

[BOJ] 백준 16637번 : 괄호 추가하기 (JAVA)

 

 

✔ 비슷한 문제 (DFS + 백트래킹)

: 괄호 문제는 DFS + 백트래킹을 좋아하나보다,,,

[백준/JAVA] 2800번: 괄호 제거