[프로그래머스]DP:N으로 표현(java)

문제보러가기

코딩테스트 연습 - N으로 표현

이문제는 dp로 분류되어있는 문제이다. dp란 작은 문제로 쪼개서 그 작은 문제를 저장해 놓았다가 다시 사용하며 답을 구하는 것이다.라고 생각했는데 처음에 이 문제가 어떻게 dp로 접근하지..? 여기부터 막혔었다..ㅎ 1개 사용 2개 사용을 이용해서 3개 사용을 할 수 있다는 것을 깨닫고 저장하여서 풀었던 문제이다! 개념이 흔들리니 문제 풀기가 막막했다는... dp알고리즘에 대한 개념을 제대로 정리해봐야겠다고 생각했다

 

 

문제풀이

-주어진 N이 1 ~ 8개로 만들 수 있는 모든 숫자를 dp에 저장한다.

-dp [i] = {dp [j] , dp [j-i]}        ->        ex) dp [3] = {dp [1] , dp [2]} , {dp [2], dp [1]} : (- , /) 연산의 경우 순서에 따라 값이 달라지므로 두 개다 연산 수행을 해야 함

-각각의 dp배열에는 Set을 지정해서 중복되지 않으면서 만들 수 있는 모든 숫자의 종류를 저장하고 다음 차례 때 이용하면서 dp배열을 채워간다.

-각각 턴마다 number이 포함되어있는지 확인해서 바로 정답을 return

 

 

 

import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
class Solution {
	//1부터 시작해서 최대 8개의 N을 이용할 수 있도록 배열크기를 잡아줌
    //Set을 지정해서 겹치는 숫자를 제외한 답만 저장할 수 있도록 함
    static HashSet<Integer>[] dp = new HashSet[9];
    public int solution(int N, int number) {
      
       if(N==number) {
			return 1;
		}
		String n_ = String.valueOf(N);
		for(int i=0;i<=8;i++) {
			dp[i] = new HashSet<Integer>();
			if(i==1) dp[1].add(Integer.parseInt(n_));
			if(i<2 ) continue;
            //ex ) dp[3]에 NNN이 들어갈 수 있도록 지정
			n_+=String.valueOf(N);
			dp[i].add(Integer.parseInt(n_));
			for(int j=1;j<i;j++) {
				 calc(j,i);
                 //찾으려는 number가 만들어졌을 경우 바로 리턴
				 if(dp[i].contains(number)) {
					 return i;
					 
				 }	
				
			}
		}
		return -1;
	}
    //각각 N의 개수마다 사칙연산을 해서 배열에 담아줌
	static void calc(int a,int b) {

		Iterator<Integer> listA = dp[a].iterator();
		Iterator<Integer> listB = dp[b-a].iterator();
		
		while(listA.hasNext()) {
			int numA = listA.next();

			while(listB.hasNext()) {
				int numB = listB.next();
				dp[b].add(numA+numB);
				dp[b].add(numA-numB);
				dp[b].add(numA*numB);
				if(numB!=0)
				dp[b].add(numA/numB);
			
			}
			listB = dp[b-a].iterator();
		}
	}
		
}