프로그래머스 동적계획법 사칙연산 JAVA 어려움

https://school.programmers.co.kr/learn/courses/30/lessons/1843

프로그래머스

 

 

1. 연산자를 제외한 숫자의 개수

int n = (arr.length + 1)/2;

 

예를들어 1 + 3 - 5 + 7 - 8 가 있으면

arr.length = 9

(9+1)/2 = 5

1, 3,5,7,8 => 5개 

 

 

2. 뺄샘 연산이 비대칭이기 때문에 maxDP 와 minDP 를 따로 저장해야 한다.

MAX- MIN 과 MIN - MAX는 다름

5-3 과 3-5 는 다른것처럼

 

int[][] maxDP = new int[n][n];
int[][] minDP = new int[n][n];

 

 

3. 배열 초기화 

for(int i=0; i < n; i++){
	maxDP[i][i] = minDP[i][i] = Integer.parseInt(arr[2*i]);
}

 

maxDP[i][j]와 minDP[i][j]는 부분 구간 [i, j]의 최댓값/최솟값을 저장하는 DP 테이블이다.

그런데 길이가 1인 구간은 그냥 숫자 그 자체가 되어야 한다.

i == j 일 때 연산할 필요 없이 자기 자신이 최댓값이자 최솟값이다.

 

만약 이 초기화를 하지 않으면?

• maxDP[i][i]와 minDP[i][i]가 초기값 0(또는 쓰레기 값)을 가지게 될 수도 있음.
• 그럼 이후 DP 계산에서 잘못된 값이 누적될 가능성이 생김.

 

1 + 3 - 5 + 7 - 8 기준 

n = 5 

DP	0	1	2	3	4
0	1
1		3
2			5
3				7
4					8

 

 

4. dp 테이블 채우는 반복문

1 ) len = 부분 문제의 크기

 

2) i 는 부분 배열의 시작점 ( 왼쪽 끝 인덱스)

j 는 부분 배열의 종료점 (오른쪽 끝 인덱스)

?

j = i + len

 

3) k 는 부분 배열을 나누는 위치 (연산자의 위치)

 

for(int k = i ; k < j ; k++){
	char op = arr[2*k + 1].charAt(0);
    
    if(op == '+') {
    	maxDP[i][j] = Math.max(maxDP[i][j] , maxDP[i][k] + maxDP[k+1][j]);
        minDP[i][j] = Math.min(minDP[i][j] , minDP[i][k] + minDP[k+1][j]);
    }else{
    	maxDP[i][j] = Math.max(maxDP[i][j], maxDP[i][j] - minDP[k+1][j]);
        minDP[i][j] = Math.min(minDP[i][j], minDP[i][k] - maxDP[k+1][j]);
    }
}

 

 

식 전체의 최댓값이 정답

maxDP[0][n-1]

 

 

 

내가 써놓고도 이해가 잘 안된다 ㅜㅜ

 

전체코드

 

class Solution {
    public int solution(String arr[]) {
        int answer = -1;
        
        int n = (arr.length + 1)/2; //숫자의 개수
        
        int[][] maxDP = new int[n][n]; //arr[i]부터 arr[j] 까지 계산했을 때 만들 수 있는 최댓값
        int[][] minDP = new int[n][n]; //arr[i]부터 arr[j] 까지 계산했을 때 만들 수 있는 최솟값
        
       for(int i=0; i < n ; i++){
            maxDP[i][i] = minDP[i][i] = Integer.parseInt(arr[2*i]);
        }
        
       for(int len = 1 ; len < n ; len++){ //부분 길이 증가
            for(int i = 0; i < n - len ; i++){ //i는 부분 배열의 시작점 (왼쪽 끝 인덱스)
                int j = i + len; // j는 부분 배열의 끝 인덱스 
                maxDP[i][j] = Integer.MIN_VALUE;
                minDP[i][j] = Integer.MAX_VALUE;
            
                for(int k = i ; k < j ; k++){
                    char op = arr[2*k +1].charAt(0);
                    if(op == '+'){
                        maxDP[i][j] = Math.max(maxDP[i][j] , maxDP[i][k] + maxDP[k+1][j]);
                        minDP[i][j] = Math.min(minDP[i][j], minDP[i][k] + minDP[k+1][j]);
                    }else{
                        maxDP[i][j] = Math.max(maxDP[i][j], maxDP[i][k] - minDP[k+1][j]);
                        minDP[i][j] = Math.min(minDP[i][j], minDP[i][k] - maxDP[k+1][j]);
                    }
                }
            }
            
        }
        
        return maxDP[0][n-1];
    }
}