190118 DP (1) N으로 표현

2019-01-18

DP (1) 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
풀이 과정
  • 아이디어가 도저히 안떠올라서 https://boycoding.tistory.com/227<-을 참조해서 풀었다 ㅜ
  • BFS를 이용해 N부터 NNNNNNNNNN까지 사칙 연산의 결과를 완전 탐색, 그 중 최소 사용 횟수를 찾아서 리턴
import java.util.*;

class Solution {
    static ArrayList<Integer> list=new ArrayList<Integer>();
    static int count=0;
    static int minCount=9;
    private void bfs(int N,int number){
        if(count>=minCount)
            return;
        if(list.size()>=minCount)
            return;
        int lastNum=(list.size()==0)?0:list.get(list.size()-1);
        
        if(lastNum==number){
            minCount=Math.min(count,minCount);
            return;
        }
        int n=0;
        int addCount=0;
        for(int i=1;i<1000000;i*=10){
            addCount++;
            if(count+addCount>=minCount)
                continue;
            n+=(N*i);
            count+=addCount;
            
            // 덧셈
            list.add(lastNum+n);
            bfs(N,number);
            list.remove(list.size()-1);
            
            // 뺄셈
            if(lastNum-n!=0){
                list.add(lastNum-n);
                bfs(N,number);
                list.remove(list.size()-1);
            }
            
            // 곱셈
            list.add(lastNum*n);
            bfs(N,number);
            list.remove(list.size()-1);
            
            // 나눗셈
            if(lastNum/n!=0){
                list.add(lastNum/n);
                bfs(N,number);
                list.remove(list.size()-1);
            }
            count-=addCount;
        }
        return;
    }
    public int solution(int N, int number) {
        bfs(N,number);
        return minCount<9?minCount:-1;
    }
}
더 나은 풀이
  • DFS를 이용해서 더 짧게 탐색할 수 있다!
class Solution {
    int answer = -1;

    public int solution(int N, int number) {
        dfs(N, 0, 0, number, "");
        return answer;
    }

    public void dfs(int n, int pos, int num, int number, String s) {
        if (pos > 8)
            return;
        if (num == number) {
            if (pos < answer || answer == -1) {
                System.out.println(s);
                answer = pos;
            }
            return;
        }
        int nn=0;
        for (int i = 0; i < 8; i++) {
            nn=nn*10+n;
            dfs(n, pos + 1+i, num + nn, number, s + "+");
            dfs(n, pos + 1+i, num - nn, number, s + "-");
            dfs(n, pos + 1+i, num * nn, number, s + "*");
            dfs(n, pos + 1+i, num / nn, number, s + "/");
        }
        // dfs(n,pos+1,num*10+n,number,s+"5");
    }
}