프로그래머스 N으로 표현

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

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

 

 

풀이 : 동적 계획법 Dynamic Programming

① N이 8개 이상이면 -1을 반환하도록 했으므로, N이 최대 8개일때까지만 계산을 수행

② N을 0~x개 사용했을 때의 결과값 각각 저장함.

   - 1) N을 0~x개 만큼 이어붙인 자연수를 저장함.

   - 2) 1)에서 저장한 케이스를 조합해 사칙연산을 수행 (N*N, N/N, NN*N .... )

         N3 = N1 사칙연산 N2 와 N2 사칙연산 N1, NN 사칙연산 N

   - 3) 2)의 결과에서 number(구하려는 값)이 나오면 연산을 중단하고 N의 갯수를 출력함.

 

[케이스 예시]

① N1

•  N

② N2

•  NN
•  N*N, N+N, N/N, N-N

③ N3

• NNN
• NN*N, NN/N , NN-N, NN+N
• N2*N, N2/N, N2-N, N2+N

 

*Nx : N이 x개인 케이스, 

 

 

 

참조

동적계획법, 위키백과

sinwoo1225, [Java] 테스트 5,8번이 통과가 안되네요.. 지적부탁드립니다. ,질문목록, N으로 표현, 프로그래머스

 

 

구현 JAVA

import java.util.*;

class Solution {
    public int solution(int N, int number) {
    	
 	 	List<HashSet<Integer>> results  = new ArrayList<>();    
        
    	String n = N+"";
    	
    	for(int i = 0; i<=8; i++) {    		
    		
    		//n이 i개일때 계산결과를 담을 HashSet을 선언
    		results.add(new HashSet<>());
    		//n을 i번 붙여서 자연수를 만들어줌 ex)5, 55, 555
    		for(int j = 1; j<=i; j++) {
    			results.get(i).add(Integer.valueOf(n.repeat(i)));    			
    		}
    			//만들어진 n에 사칙연산을 수행.
    			for(int k = 0; k < i; k++) {
    				for(int a : results.get(k)) {
    					for(int b : results.get(i-k)) {
    						results.get(i).add(a+b);
    						results.get(i).add(a*b);
    						results.get(i).add(a-b);
    						if(b>0) {
    							results.get(i).add(a/b);
    						}
    					}
    				}
    			}
    		
    		
    		if(results.get(i).contains(number)){
    			return i;
    		}
    		
    	}
    	return -1;
    }
    
}