프로그래머스 동적계획법(Dynamic Programming) N으로 표현 자바

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

프로그래머스

 

 

1. HashSet 8개를 가진 ArrayList를 만들어준다.

(HashSet은 중복을 불허한다.)

각각의 HashSet 은 숫자 n 개로 만들 수 있는 값을 다 담고 있다. 

5가 주어졌을 때 

1개로 만들 수 있는 숫자들 = 5 

2개로 만들 수 있는 숫자들 = 5 + 5 or 5 -5 or 5*5 or 5/5 or 55

3개로 만들 수 있는 숫자들= 1개로 만들 수 있는 숫자  ( + - * / ) 2개로 만들 수 있는 숫자

                                             2개로 만들 수 있는 숫자 ( 사칙연산 ) 1개로 만들 수 있는 숫자

                                             555

4개로 만들 수 있는 숫자들 = 2개 * 2개 or 1개 * 3개 or 3개 * 1개  or 5555

...

 

2. 숫자 1개일 때는 무조건 자기 자신밖에 안나와서 첫번째 hashset은 설정해놓을 수 있다.

3. 만약  N과 number이 같으면 그냥 1값 리턴해주면 된다.

4. n회 반복된 수를 구할 때는 Integer을 string으로 바꾼 후 repeat을 해준 다음 다시 Integer형으로 바꿔준다.

5. 사칙연산을 할 때는 0으로 나눌 수 없으니 조건을 넣어준다.

6. 만약 number과 같은 값이 있다면 바로 return (숫자가 제일 적게 쓰여야 하니까)

7. 없으면 -1 return 

import java.util.*;

class Solution{

	public int solution(int N, int number){
    	
        int answer = -1;
        
        if(N == number) return 1;
        
        List<HashSet<Integer>> list = new ArrayList<>();
        
        for(int i=0; i<9; i++){
        	list.add(new HashSet<Integer>());
        }
        
        list.get(1).add(N);
        
        for(int i=2 ; i<9 ; i++){
        
        	HashSet<Integer> tmp = list.get(i);
            
            for(int j=1 ; j < i ; j++) {
            
            	HashSet<Integer> a = list.get(i);
                HashSet<Integer> b = list.get(i-j);
                
                for(int x : a) {
                	for(int y : b){
                    	tmp.add(x+y);
                        tmp.add(x-y);
                        tmp.add(x*y);
                        tmp.add(-x+y);
                        tmp.add(-x-y);
                        tmp.add(-x*y);
                        if( x!=0 && y!=0 ) {
                        	tmp.add(x/y);
                            tmp.add(-x/y);
                        }
                    }
                }
            
            }
            
            tmp.add(Integer.parseInt(String.valueOf(N).repeat(i)));
            if(tmp.contains(number)) return i;
        
        }
    
    	return answer;
    }

}