프로그래머스 스쿨(Java - Lv.2) - 완전범죄[DP - 메모아이징]

문제

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

 

 

 

해답

import java.util.*;

class Solution {
    public int solution(int[][] info, int n, int m) {
        Set<String> dupChk = new HashSet<>();
        Queue<int[]> que = new LinkedList<>();
        int min = Integer.MAX_VALUE;
        int index = 0;
        que.add(new int[]{-1,0,0});
        while(!que.isEmpty()){
            int[] arr = que.poll();
            index = arr[0]+1;
            //마지막에 도달했을 경우
            if(index==info.length){
                min = (min>arr[1])?arr[1]:min;
                continue;
            }
            
            //반복탐색
            int[] tempA = new int[]{index,arr[1]+info[index][0],arr[2]};
            String key = tempA[0]+"_"+tempA[1]+"_"+tempA[2];
            
            if(tempA[1]<n && !dupChk.contains(key)){
                dupChk.add(key);
                que.add(tempA);
            }
            
            int[] tempB = new int[]{index,arr[1],arr[2]+info[index][1]};
            key = tempB[0]+"_"+tempB[1]+"_"+tempB[2];
            
            if(tempB[2]<m && !dupChk.contains(key)){
                dupChk.add(key);
                que.add(tempB);
            }
        }
        
        if(min==Integer.MAX_VALUE) min = -1;
        return min;
    }
}

 

 

해설

 

최적의 해를 찾기위해서 이진트리방식을 선택하되, 중복을 제거하는 방향으로 문제를 풀었다.

 

매번 2가지로 갈라지는 모든 경우의수를 계산할수 없으며, 기준을 벗어난 것들을 제거하기위해서

 

이진트리를 que를 이용해 bfs를 사용해 index레벨이 최고가 될때까지 순회하며, Set를 이용해

 

현재의 상태를 string화 하여 key가 중복일 경우 더이상 처리하지 않도록 하였다.

 

중복처리에 대해서 고민을 길게하였으나, 간단하게 String으로 처리하는것이 의외로 좋은 방법이었다.