[JAVA] 프로그래머스 - N으로 표현

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

 

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N  number  return

5	12	4
2	11	3

 

문제풀이

 

class Solution {
    public int solution(int N, int number) {
        int answer = 0;
        int answerlist=0;
        int sum=0;
        Vector<Integer>v = new Vector<>();
        
        if(number/N<N){
            sum+=N;
            answerlist++;
        }else{
            v.add(1,answerlist);
        }

처음엔 이런식의 방법을 떠올렸는데 길게 생각해보지 않아도 일일히

answerlist를 초기화하는 번거로움 등이 최적 코드가 아닐 것이라고 생각이 되었음.

또한 NN같은 경우를 N*10+N , N*100+N*10+N .....어떻게 코드로 처리할지가 매우 관건이었다.

 

 

 

생각하다가 답이 안나와서 검색을 하다보니 dfs로 풀 수 있구나를 알았음.

그 전에 왜 애초에 재귀를 생각하지 않았을까..... 

'최솟값이 8보다 크면.. ' 이 부분도 그냥 재귀, dfs 안에 if문으로 넣어두면

쉽게 거를 수 있었다.

 

public class Sol10 {
	int answer = -1;
	
    public int solution(int N, int number) {
        
    	
    	if(N == number) {
    		return 1;
    	}
        
    	dfs(N,number,1, N);
        
        return answer;
    }
    
    
    private void dfs(int N, int number, int count, int value) {
    	
    	if(count > 8) {
    		return;    		
    	}
    	
    	if( count < answer || answer == -1) {
    		if(value == number ) {
    			answer = count; 
    			return;
    		}
    	}
    		
    	int temp = N;
    	
  
    	for(int i = 0; i<8-count; i++ ) {
    		dfs(N,number,count+1+i, value+temp);
        	dfs(N,number,count+1+i, value-temp);
        	dfs(N,number,count+1+i, value*temp); 
        	dfs(N,number,count+1+i, value/temp);
        	
        	temp = (temp*10)+N;
        	
    	}
    }

}