프로그래머스 사칙연산

접근

프로그래머스 사칙연산을 풀려면 여기를 클릭하세요

이 문제는 dp를 통해서 풀어야 한다.

처음에 나는 a-b 경우 최대-최소 / a+b 경우 최대+최대 여기까지 접근이 가능했다. 하지만 이후에 어디서 dp를 사용해야 하는지 감을 잡지 못했고 결국 다른 사람의 풀이를 참고 했다.

하지만 여전히 왜 dp를 사용해야 하는지 이유를 알지 못했고 그림을 그리면서 해결되었다.
어디서 dp가 등장하는가에 대한 의문은 아래 그림을 통해서 설명하고자 한다.

보면 처음 1번에서 구한 3개의 덩어리의 결과를
2번에서 그대로 이용한다.
따라서 DP가 사용된다.

일단 이 규칙을 발견했으니 구현을 해보자
먼저 해야할 일은 쪼개는 일이다.
DP라는 것은 작은 부분을 최적을 모아 큰 문제를 최적으로 해결하는 것이고 TOP-DOWN과 BOTTOM-UP이 있는데 이 문제에서는 TOP-DOWN을 사용한다.

DP는 그냥 저장소의 개념이고 저 저장소의 어떤 값을 저장할 것인가에 대해서는 메서드를 통해서 저장해야 한다. 또한 TOP-DOWN이기 때문에 이 메서드는 재궈적으로 호출된다. 가장 큰 문제가 가장 작은 단위의 매개변수를 갖는 매서드를 재귀적으로 호출하는 것이다.

과정

먼저 규칙이 있다
최대 + 최대 -> 최대 + (최대 - 최소)
최대 - 최소 -> 최대 - (최소 + 최소)

등 가운데에 있는 연산자에 따라서 앞에 최대가 와야하는지 최소가 와야 하는지 결정되고
그 덩어리 안에 또 연산자가 있다면 거기 안에서도 조건 안에서 연산자에 따라 최대, 최소가 결정된다.

따라서 최대인지, 최소인지 결정할 수 있는 flag가 필요하다.

또한 어디에서 부터 어디까지 쪼갤것인지 표시해주는 start, end에 대한 값이 필요하다.

마지막으로 연산자와 숫자를 구분해줄 담는 저장소가 필요하다.

자바코드

https://countrysides.tistory.com/86
이 분의 풀이에 힌트를 얻어 작성했다.

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



//a-b 최대 - 최소
//a+b 최대 + 최대

class Solution {
    static int[] num;
    static char[] oper;

    static int[][][] dp;

    static String[] arr;

    static int tmp = 987654321;

    public int solution(String arr[]) {
        dp = new int[2][150][150];// 최대 최소 2

        this.arr =arr;
        for(String x : arr){
            System.out.println("x:"+x);
        }
        init();
        int answer = solve(0,0,arr.length/2); // oper과 numm을 통해서
        return answer;
        
    }
    //초기화 작업: 숫자와 연산자를 구별, dp 초기화
    public void init(){
        int n = arr.length/2;

        for(int i=0;i<n+1;i++){
            for(int j=0;j<n+1;j++){
                dp[0][i][j] = -1*tmp;//최대
                dp[1][i][j] = tmp;//최소
            }
        }

        num = new int[n+1];
        oper = new char[n];

        //짝수는 숫자, 홀수는 연산자
        for(int i=0;i<arr.length;i++){
            if(i%2==0) num[i/2] = Integer.parseInt(arr[i]);
            else oper[i/2] = arr[i].charAt(0);
        }
        
        for(int x : num){
            System.out.println("num:"+num);
        }
        for(char x: oper){
            System.out.println("oper:"+oper);
        }

    }

    static int solve(int flag , int start, int end){
        //마지막 지점인 숫자에 도달, 가장 작은 단위의 dp
        if(start==end){
            return dp[flag][start][end]=num[start];
        }
        // 앞서 계산된 것들이라면
        if(flag==0 && dp[flag][start][end]!= -1*tmp)
            return  dp[flag][start][end];
        if (flag==1 && dp[flag][start][end]!= tmp)
            return  dp[flag][start][end];

        int ret = (flag == 0) ? -1 * tmp : tmp;//이 ret 값은 계속 갱신됩니다. 갱신되는 값 중에서 가장 큰 값, 작은 값을 찾는 것이 관건

       // dp[flag][start][end] = 0;

        if(flag==0){
            for(int mid = start ; mid<end;mid++){// 이 for문 안에서 ret 값은 계속 갱신된다.
                if(oper[mid]=='-'){
                  ret   = Math.max(ret,solve(0,start,mid) -solve(1,mid+1,end));
                }else{
                   ret    =Math.max(ret,solve(0,start,mid) + solve(0,mid+1,end));
                }
            }
        }//if flag==0
        else{
            for(int mid = start ; mid<end;mid++){// 이 for문 안에서 ret 값은 계속 갱신된다.
                if(oper[mid]=='-'){
                   ret  = Math.min(ret,solve(1,start,mid)-solve(0,mid+1,end));
                }else{
                    ret  = Math.min(ret,solve(1,start,mid)+solve(1,mid+1,end));
                }
            }

        }//if flag ==1
        
        System.out.println("flag:"+flag+"start:"+start+"end"+end+"최종"+ret);

        return dp[flag][start][end]=ret;

    }
}