[프로그래머스-1843] 사칙연산

[DP-사칙연산]

프로그래머스

 

문제

사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않는다. 즉, 빼기는 연산 순서에 따라 계산 결과가 달라진다. 문자열 형태의 숫자와, '+', '-'가 들어있는 배열이 매개변수로 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓닶 return하는 solution 함수 완성하기

 

제한사항

• arr는 두 연산자와 숫자가 들어있는 배열이며, 길이는 3 이상 201 이하이다.
  • arr의 길이는 항상 홀수
  • arr에 들어있는 숫자의 개수는 2개 이상 101개 이하이며, 연산자의 개수는 -1이다.
  • 숫자는 1 이상 1,000 이하의 자연수가 문자열 형태로 들어있다
• 배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있다.

입출력 예시

arr = ["1", "-", "3", "+", "5", "-", "8"], result = 1

arr = ["5", "-", "3", "+", "1", "+", "2", "-", "4"], result = 3

문제 접근

DFS로 풀기에는 시간초과가 날 듯한 문제인 듯하고, DP로 접근하기에 방법을 모르겠어서 다른 사람의 풀이를 참고해서 풀었다..ㅠ

이 문제는 두 가지 DP 배열이 필요하다. 최댓값 DP와 최솟값 DP

DP[i][j] = i번째부터 j번째까지의 연산 결과

 

또한, 연산자가 '+'인 경우와 '-'인 경우 최댓값과 최솟값을 갱신시켜주는 연산이 다르다.

1) +인 경우

• 최대 = 최대 + 최대
• 최소 = 최소 + 최소

2) -인 경우

• 최대 = 최대 - 최소
• 최소 = 최소 - 최대

위 내용을 토대로 예시를 근거로 접근해보면,

0	1	2	3	4	5	6
1	-	3	+	5	-	8

 

1. 처음에 본인 자신, 즉 i번째-i번째는 해당 숫자 채우기(min_dp, max_dp)

min_dp

	0	1	2	3	4	5	6
0	1	x		x		x
1	x	x	x	x	x	x	x
2		x	3	x		x
3	x	x	x	x	x	x	x
4		x		x	5	x
5	x	x	x	x	x	x	x
6		x		x		x	8

 

max_dp

	0	1	2	3	4	5	6
0	1	x		x		x
1	x	x	x	x	x	x	x
2	x	x	3	x		x
3	x	x	x	x	x	x	x
4	x	x	x	x	5	x
5	x	x	x	x	x	x	x
6	x	x	x	x	x	x	8

 

2. 3자리부터 arr 배열 길이 자리까지 사칙연산 계산

2-1) 3자리씩 먼저 확인 -> 1-3, 3+5, 5-8

 

min_dp

	0	1	2	3	4	5	6
0	1	x	-2	x		x
1	x	x	x	x	x	x	x
2	x	x	3	x	8	x
3	x	x	x	x	x	x	x
4	x	x	x	x	5	x	-3
5	x	x	x	x	x	x	x
6	x	x	x	x	x	x	8

 

max_dp

	0	1	2	3	4	5	6
0	1	x	-2	x		x
1	x	x	x	x	x	x	x
2	x	x	3	x	8	x
3	x	x	x	x	x	x	x
4	x	x	x	x	5	x	-3
5	x	x	x	x	x	x	x
6	x	x	x	x	x	x	8

 

2-2) 3자리씩 확인 -> 1-3+5, 3+5-8 -> 1-(3+5) or (1-3)+5 / 3+(5-8) or (3+5)-8

min_dp

	0	1	2	3	4	5	6
0	1	x	-2	x	-7	x
1	x	x	x	x	x	x	x
2	x	x	3	x	8	x	0
3	x	x	x	x	x	x	x
4	x	x	x	x	5	x	-3
5	x	x	x	x	x	x	x
6	x	x	x	x	x	x	8

 

max_dp

	0	1	2	3	4	5	6
0	1	x	-2	x	3	x
1	x	x	x	x	x	x	x
2	x	x	3	x	8	x	0
3	x	x	x	x	x	x	x
4	x	x	x	x	5	x	-3
5	x	x	x	x	x	x	x
6	x	x	x	x	x	x	8

 

2-3) 4자리씩 확인 -> 1-3+5-8 -> 1-(3+5-8) or (1-3)+(5-8) or (1-3+5)-8

min_dp

	0	1	2	3	4	5	6
0	1	x	-2	x	-7	x	-15
1	x	x	x	x	x	x	x
2	x	x	3	x	8	x	0
3	x	x	x	x	x	x	x
4	x	x	x	x	5	x	-3
5	x	x	x	x	x	x	x
6	x	x	x	x	x	x	8

 

max_dp

	0	1	2	3	4	5	6
0	1	x	-2	x	3	x	1
1	x	x	x	x	x	x	x
2	x	x	3	x	8	x	0
3	x	x	x	x	x	x	x
4	x	x	x	x	5	x	-3
5	x	x	x	x	x	x	x
6	x	x	x	x	x	x	8

 

3) 최종적으로 max_dp[0][arr배열 길이-1] 리턴

코드

function solution(arr) {
    var answer = -1;
    const len = arr.length;
    // DP[i][j] = i번째부터 j번째까지의 연산
    const max_dp = Array.from({length: len}, () => Array.from({length: len}, () => 0)); // 최댓값 DP
    const min_dp = Array.from({length: len}, () => Array.from({length: len}, () => Number.MAX_SAFE_INTEGER)); // 최솟값 DP
    
    // DP[i][i] = 본인 자신은 그대로임
    for(let i=0; i<arr.length; i+=2) {
        max_dp[i][i] = +arr[i];
        min_dp[i][i] = +arr[i];
    } 
    
    for(let count=3; count<len+1;count+=2){
        for(let left=0; left<len-2; left+=2){
            let right = left+count-1;
            if(right >= len) break;
            
            const candidates = [];
            for(let operation=left+1; operation<right; operation+=2) {
                if(arr[operation] === '+') {
                    // 최대 = 최대+최대
                    candidates.push(max_dp[left][operation-1]+max_dp[operation+1][right]);
                    // 최소 = 최소+최소
                    candidates.push(min_dp[left][operation-1]+min_dp[operation+1][right]);
                }else {
                    // 최대 = 최대-최소
                    candidates.push(max_dp[left][operation-1]-min_dp[operation+1][right]);
                    // 최소 = 최소-최대
                    candidates.push(min_dp[left][operation-1]-max_dp[operation+1][right]);
                }
            }
            max_dp[left][right] = Math.max(...candidates);
            min_dp[left][right] = Math.min(...candidates);
        }
    }
    return max_dp[0][len-1];
}