[백준, JAVA]16639번, 괄호 추가하기 3

문제 링크

16639번: 괄호 추가하기 3

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

이 문제에 핵심

1. 주어진 수식에서 괄호를 추가해서 가장 큰 값을 결과로 출력합니다.

2. 수식에는 0~9까지의 정수와 연산자는 +, -, * 만 사용됩니다.

3. 괄호의 생성은 제한이 없으며 추가하지 않아도 상관 없습니다.

 

 

각 수식의 구간에 최대값과 최소값을 DP[][]에 저장 및 이용하여 전체 수식의 최대값을 구하였습니다.

 

덧셈( + )

최대값

= 구간1의 최대값 + 구간2의 최대값

 

최소값= 구간1의 최소값 + 구간2의 최소값

 

뺄셈( - )

최대값

= 구간1의 최대값 - 구간2의 최소값

 

최소값

= 구간1의 최소값 - 구간2의 최대값

 

곱셈( - )

1. 구간1의 최대값 * 구간2의 최소값

2. 구간1의 최대값 * 구간2의 최대값

3. 구간1의 최소값 * 구간2의 최소값

4. 구간1의 최소값 * 구간2의 최대값

 

최대값

= 1, 2, 3, 4의 값이 가장 큰 값

 

최소값

= 1, 2, 3, 4의 값이 가장 작은 값

 

 

예제입력 3.

수식 : 8*3+5+2

	1	2	3	4
1	(8, 8)
2	x	(3, 3)
3	x	x	(5, 5)
4	x	x	x	(2, 2)

 

(1 ~ 2)범위의 최대값과 최소값 구하기

나올 수 있는 구역 : (1~2)

(1~2)에서 사용되는 연산자 : *

 

	1	2	3	4
1	(8, 8)	(24, 24)
2	x	(3, 3)
3	x	x	(5, 5)
4	x	x	x	(2, 2)

 

(2 ~ 3)범위의 최대값 최소값 구하기

나올 수 있는 구역 : (2~3)

(2~3)에서 사용되는 연산자 : +

	1	2	3	4
1	(8, 8)	(24, 24)
2	x	(3, 3)	(8, 8)
3	x	x	(5, 5)
4	x	x	x	(2, 2)

(1 ~ 3)범위의 최대값 최소값 구하기

나올 수 있는 구역 : (1~1) + (2 ~ 3), (1 ~ 2) + (3 ~ 3) 

(1~1) + (2 ~ 3)에서 사용되는 연산자 : *

(1~2) + (3 ~ 3)에서 사용되는 연산자 : +

	1	2	3	4
1	(8, 8)	(24, 24)	(64, 29)
2	x	(3, 3)	(8, 8)
3	x	x	(5, 5)
4	x	x	x	(2, 2)

이후 탐색.....

	1	2	3	4
1	(8, 8)	(24, 24)	(64, 29)	(80, 31)
2	x	(3, 3)	(8, 8)	(10, 10)
3	x	x	(5, 5)	(7, 7)
4	x	x	x	(2, 2)

 

(1~4)의 최대값이 수식의 최대값으로써 결과로 80을 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• String.charAt()을 이용해서 수식의 연산자와 숫자를 나누었습니다.
• 각 DP[][]의 최대값과 최소값을 구하는 cal함수를 실행하였습니다.
• 수식의 대한 최대값을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal는 연산자에 따른 구역별 최대값과 최소값을 비교하여 저장하는 함수입니다.

 

import java.util.*;
import java.io.*;

public class Main {
	//DP관련 클래스
    static class dpValue{
        int max,min;
        public dpValue(int max, int min) {
            this.max = max;
            this.min = min;
        }
    }
    static int N;
    static ArrayList<Integer> num = new ArrayList<>();	//수식의 숫자 저장 리스트
    static ArrayList<Character> operator = new ArrayList<>();	//수식의 연산자 저장 리스트
    static dpValue[][] DP;		//각 구간의 최대값, 최소값 저장하는 메모이제이션
    static public void  main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        N = Integer.parseInt(br.readLine());
        int size = N/2+2;
        DP = new dpValue[size][size];

        String str = br.readLine();
        for(int i=1;i<=N;i++){
            if(i%2==1){		//수식 숫자 저장
                int temp = Character.getNumericValue(str.charAt(i-1));
                num.add(temp);
                int index = i/2+1;
                DP[index][index] = new dpValue(temp,temp);
            } else		//수식 연산자 저장
                operator.add(str.charAt(i-1));
        }
        //각 구간별 DP[][]값 구하기
        for(int i=2;i<size;i++){
            for(int j=i-1;j>0;j--){
                cal(i,j);
            }
        }
        bw.write(DP[1][size-1].max + "");	//수식 최대값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //DP[][] 최대값 최소값 구하는 함수
    static void cal(int x, int y){
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for(int i=0;i<x-y;i++){
            dpValue value1 = DP[y+i+1][x];
            dpValue value2 = DP[y][y+i];
            int operatorIndex = y+i-1;
            if(operator.get(operatorIndex) == '+'){	//사용 연산자 '+'
                max = Math.max(max,value1.max + value2.max);
                min = Math.min(min,value1.min + value2.min);
            }else if(operator.get(operatorIndex)=='-'){	//사용 연산자 '-'
                max = Math.max(value2.max - value1.min, max);
                min = Math.min(value2.min - value1.max,min);
            }else{		//사용 연산자 '*'
                int temp = value1.max * value2.max;
                int tempMin = temp;
                int tempMax = temp;

                temp = value1.max * value2.min;
                tempMax = Math.max(temp,tempMax);
                tempMin = Math.min(temp,tempMin);

                temp = value1.min * value2.max;
                tempMax = Math.max(temp,tempMax);
                tempMin = Math.min(temp,tempMin);

                temp = value1.min * value2.min;
                tempMax = Math.max(temp,tempMax);
                tempMin = Math.min(temp,tempMin);

                max = Math.max(max,tempMax);
                min = Math.min(min,tempMin);
            }
        }
        DP[y][x] = new dpValue(max,min);		//최대값, 최소값 저장
    }
}