[백준] 16637번 - 괄호 추가

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

16637번: 괄호 추가하기

 

완탐을 할때에는 인덱스를 기반으로 해서 탐색을 할 생각을 해야한다.

풀이를 보고 풀었다..!

 

문제 접근

괄호를 씌워주는 방식은 크게 2가지가 존재한다.

(1) 앞의 부분을 먼저 계산해주고, 뒤의 부분을 계산하기

(2) 뒤의 부분을 먼저 계산해주고, 앞의 부분을 계산하기

 

(1),(2)를 행한뒤 재귀호출을 하여 식이 끝날때까지 다음 계산을 계속 해주면 된다.

최종적으로 수식이 끝나는 경우 max값을 찾아 재귀 호출을 종료해준다.

 

말이 쉽지.. 이걸 코드로 어떻게 짤까..?

 

 

1차 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {

    public static ArrayList<Character> oper_str;
    public static ArrayList<Integer> nums;

    public static int N, res;
    public static String s;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        s = br.readLine();

        oper_str = new ArrayList<>();
        nums = new ArrayList<>();

        // 숫자와 문자 분리
        for (int i = 0; i < N; i++) {
            if (i % 2 == 0) { // 숫자인 경우
                nums.add(Character.getNumericValue(s.charAt(i)));
            } else { // 문자인 경우
                oper_str.add(s.charAt(i));
            }
        }

        go(0, nums.get(0));

        bw.write(res + "\n");
        bw.close();
        br.close();
    }

    public static void go(int here, int num) {
        if (here == nums.size() - 1) {
            res = Math.max(res, num);
            return;
        }

        // 2가지 경우로 나뉜다.

        // 앞의 값 먼저 계산
        go(here + 1, oper(oper_str.get(here), num, nums.get(here + 1)));

        // 뒤에꺼 괄호해주기(마지막 값) - 오버플로우 체크
        if (here + 2 <= nums.size() - 1) {
            int tmp = oper(oper_str.get(here + 1), nums.get(here + 1), nums.get(here + 2)); // 뒤에 먼저 계산하고
            go(here + 2, oper(oper_str.get(here), num, tmp)); // 앞의 값 같이 계산하기
        }
    }

    public static int oper(char a, int b, int c) {
        if (a == '+') {
            return b + c;
        }
        if (a == '-') {
            return b - c;
        }
        return b * c;
    }
}

 

무엇이 문제였을까?

음수가 나오는 경우도 고려해서 res의 초기값을 0으로 잡는 것이 아닌 int형의 최솟값으로 잡아주어야 한다.

 

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {

    public static ArrayList<Character> oper_str;
    public static ArrayList<Integer> nums;

    public static int N, res;
    public static String s;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        s = br.readLine();

        oper_str = new ArrayList<>();
        nums = new ArrayList<>();
        res = Integer.MIN_VALUE;

        // 숫자와 문자 분리
        for (int i = 0; i < N; i++) {
            if (i % 2 == 0) { // 숫자인 경우
                nums.add(Character.getNumericValue(s.charAt(i)));
            } else { // 문자인 경우
                oper_str.add(s.charAt(i));
            }
        }

        go(0, nums.get(0));

        bw.write(res + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static void go(int here, int num) {
        if (here == nums.size() - 1) {
            res = Math.max(res, num);
            return;
        }

        // 2가지 경우로 나뉜다.

        // 앞의 값 먼저 계산
        go(here + 1, oper(oper_str.get(here), num, nums.get(here + 1)));

        // 뒤에꺼 괄호해주기(마지막 값) - 오버플로우 체크
        if (here + 2 <= nums.size() - 1) {
            int tmp = oper(oper_str.get(here + 1), nums.get(here + 1), nums.get(here + 2)); // 뒤에 먼저 계산하고
            go(here + 2, oper(oper_str.get(here), num, tmp)); // 앞의 값 같이 계산하기
        }
    }

    public static int oper(char a, int b, int c) {
        if (a == '+') {
            return b + c;
        }
        if (a == '-') {
            return b - c;
        }
        return b * c;
    }
}