[세모] 프로그래머스 완전범죄 // dp, void dfs dp

https://school.programmers.co.kr/learn/courses/30/lessons/389480?language=java

프로그래머스

* 내풀이

A가훔치기, B가훔치기 OX퀴즈 -> 2^40 -> 시간초과 -> dp 필요

int dfs로 변경 && 메모

참고로 dp 초기화부분을 상수시간 최적화해야 통과함..? 맞게푼건지? (재귀dp 억까?)

import java.util.*;

class Solution {
    static int n,m,ret=Integer.MAX_VALUE;
    // static int dp[][][] = new int[44][124][124]; //값 : 그때 a가 남긴 흔적 갯수 최소값
    static Integer[][][] dp;
    
    //(idx, 남은흔적갯수)
    int dfs(int idx, int a, int b, int[][] info){
        // System.out.println(idx+" "+a+" "+b);
        if(a<=0 || b<=0){ //0도 안됨
            return Integer.MAX_VALUE; //배제
        }
        
        if(idx==info.length){
            // System.out.println("갱신: "+idx+" "+a+" "+b);
            // ret=Math.min(ret,Math.abs(n-a));
            return Math.abs(n-a);
        }
        
        if(dp[idx][a][b]!=null){
            return dp[idx][a][b];
        }
        
        int ret = Integer.MAX_VALUE;
        
        // ret=0;
        ret=Math.min(ret, dfs(idx+1,a-info[idx][0],b,info));
        ret=Math.min(ret,dfs(idx+1,a,b-info[idx][1],info));
        
        dp[idx][a][b]=ret;
        return ret;
    }
    
    public int solution(int[][] info, int _n, int _m) {
        n=_n; m=_m;
        // double a = Math.pow(2,40);
        // System.out.println(a);
        
        // for(int i=0;i<44;++i){
        //     for(int j=0;j<124;++j){
        //         for(int k=0;k<124;++k){
        //             dp[i][j][k]=Integer.MAX_VALUE;
        //         }
        //     }
        // }
        // 필요한 크기만큼만 DP 배열 초기화 (null로 초기화됨)
        dp = new Integer[info.length + 1][n + 1][m + 1];
        
        ret = dfs(0,n,m,info);
        
        if(ret==Integer.MAX_VALUE) return -1;
        return ret;
    }
}

 

* 새로운방법

다른풀이중 void dfs로 dp를 할수있는 방법을 찾았다!

상태를 HashSet에 문자열로 저장하고, 이미 방문한상태면 그냥 리턴을 때려버리면 된다!

answer은 void dfs처럼 static으로 두고 갱신하면 된다!

import java.util.*;
class Solution {
    public static int len;
    public static int answer=Integer.MAX_VALUE;
    public static Set<String> visited = new HashSet<>();
    public int solution(int[][] info, int n, int m) {
        // Arrays.sort(info, (a, b) -> (b[0] + b[1]) - (a[0] + a[1]));
        // for(int [] i: info){
        //     System.out.println(i[0]+" "+i[1]);
        // }
        len=info.length;
        dfs(info,n,m,0,0,0);
        if(answer==Integer.MAX_VALUE){
            return -1;
        }
        return answer;
        //dfs인데 이미 기존의 최솟값보다 커진 경우 BREAK
        //만약 이미 sumA가 크거나 같다면 

    }
    public void dfs(int [][] info, int n, int m, int sumA, int sumB, int depth){
        if(sumA>=n || sumB >=m || sumA >=answer){
            return;
        }
        if(depth==len){
            //calc
            answer=Math.min(answer,sumA);
            return;
        }

        String state = sumA + "," + sumB + "," + depth;
        if (visited.contains(state)) return;

        visited.add(state);
        //a가 포함하는 경우
        dfs(info,n,m, sumA+info[depth][0], sumB, depth+1);
        //b가 포함하는 경우
        dfs(info,n,m, sumA, sumB+info[depth][1], depth+1);

    }
}