[JS] 사칙연산

까다로운 DP문제였다.

 

 

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

프로그래머스

 

 

이전부터 느낀거지만 이런 유형의 DP가 정말 까다로운 것 같다.

 

 

문제에서 제공한 1번예제를 분석해보면서 풀이를 생각해보자.

 

["1", "-", "3", "+", "5", "-", "8"]

 

먼저 i,j를 왼쪽부터의 인덱스라고 생각해보자. 예를들어

 

i : 0, j : 1 이라면 1-3까지를 나타낸다고 생각해보자.

 

그리고 i와 j의 차를 step이라고 생각해보자.

 

i	j	수
0	0	1
1	1	3
2	2	5
3	3	8

 

 

위 표와 같이 i와 j가 같은경우 즉 step이 1인 경우에는 자기자신밖에 없으므로 경우의 수가 하나인 점을 알 수 있다.

 

한걸음 더 확장해서 i와 j가 1차이 나는 경우도 마찬가지다.

 

1-3 , 3+5, 5-8 또한 경우의 수가 한개가 나오게 된다.

 

 

 

이제 DP를 2개 만들어 보자.

 

min[i][j] -> i,j인 경우의 최솟 값

max[i][j] -> i,j인 경우의 최대 값

 

어차피 step이 1인경우까지는 min과 max에 같은 값이 차게 된다.

 

 

 

 

이제 i와 j가 2차이 나는 경우를 보자.

 

i=0, j=2인 경우인 1-3+5를 보자. 

 

이는 

 

[ 1 ] - [ 3 + 5 ] 와  [ 1 - 3 ] + [ 5 ]로 나눌 수 있다.

 

 

 

이때! 중요한 점은 필자가 ( ) 가 아닌 [ ] 를 사용했다는 점이다. 여기서 [ ] 는 단순히 수학적 의미의 괄호가 아닌, 3+5로 만들 수 있는 최댓값을 의미한다. 따라서

 

[ 1 ] - [ 3 + 5 ] => max[0][0] - min[1][2]

[ 1 - 3 ] + [ 5 ] => max[0][1] + max[2][2]

 

와 같이 나타낼 수 있다.

 

 

여기서 왜 DP를 두개 둬야 하는지 알 수 있다. -인 경우에는 뒤에 오는값이 최솟값이 와야 결국에 최대값을 채울 수 있기 때문이다.

이 과정을 반복해서 DP를 채워나간다면 결국

 

max[0][len-1] 에는 우리가 원하는 정답이 채워진다.

 

 

 

 

 

function solution(arr) {
    const nums = []
    const symbol = []
    for (const st of arr){
        if(st==="-" || st==="+") symbol.push(st)
        else nums.push(+st)
    }
    
    const len = ~~(arr.length/2) + 1
    const min = [...Array(len)].map(_ => Array(len).fill(Infinity))
    const max = [...Array(len)].map(_ => Array(len).fill(-Infinity))
    
    for(let step = 0 ; step < len ; step++){
        for(let i = 0 ; i < len-step ; i++){
            const j = i + step
            if(step===0){
                min[i][j] = nums[i]
                max[i][j] = nums[i]
                continue
            }
            for(let k = i ; k < j ; k++){
                if(symbol[k]==='+'){
                    min[i][j] = Math.min(min[i][j],min[i][k]+min[k+1][j])
                    max[i][j] = Math.max(max[i][j],max[i][k]+max[k+1][j])
                } else if (symbol[k]==='-') {
                    min[i][j] = Math.min(min[i][j],min[i][k]-max[k+1][j])
                    max[i][j] = Math.max(max[i][j],max[i][k]-min[k+1][j])
                } 
            }
        }
    }
    
    return max[0][len-1]
}