[pro] 프로그래머스 level3 42895 N으로 표현 (Java) - dp

[문제]

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

프로그래머스

 

[풀이]

dfs로 완전탐색하여 푸는 방법을 먼저 생각했으나 dp 카테고리에 있는 걸 봐버려서 더 효율적으로 푸는 방법이 있겠군 싶었다..dp로 풀어야 한다는 걸 알아도 생각이 안나는게 문제지만ㅠ

 

N이 사용된 횟수를 기준으로 한다. N이 사용된 횟수가 1번이면 N 자신밖에 없을 것이다. 

2번이면 N+N, N-N, N*N, N/N, NN 등이 있을 것이다. 

그렇다면 N이 사용된 횟수가 3번이면? 4번이면..?

여기서 dp를 사용한다. dp를 이용하면 이전에 구한 값을 재활용해서 더 큰 경우의 값을 구할 수 있다.

따라서 N이 사용된 횟수가 3번이라면 이전에 구한 1번과 2번의 모든 경우에 대하여 +, -, *, / 를 한 값을 저장하면 될 것이다.

이때 주의할 것은 괄호가 있기 때문에 1번+2번과 2번+1번을 따로 고려해주어야 한다는 것이다. 예를 들어, 5 - (5*5) 와 (5*5) - 5 는 다른 값이 나온다.

 

N이 사용된 횟수가 적은 경우부터 차례대로 계산해주기 때문에 number가 포함된다면 바로 그 사용 횟수를 정답으로 반환해주었다. 또한 중복 연산값을 제외해주기 위해 Set을 사용했다.

 

풀이 참고: https://born2bedeveloper.tistory.com/38

 

[코드]

 

import java.util.*;

class Solution {
    Set<Integer>[] set = new HashSet[9];
    public int solution(int N, int number) {
        int answer = 0;
        //N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 
        
        //사칙연산이 아닌 수 넣어주기 N, NN, NNN...
        int num = 0;
        for(int i=1; i<=8; i++){
            num = num*10 + N;
            set[i] = new HashSet<>();
            set[i].add(num);
        }
        
        if(N==number) return 1;
        
        for(int i=2; i<=8; i++){
            for(int j=1; j<i; j++){
                for(Integer a : set[j]){
                    for(Integer b: set[i-j]){
                        set[i].add(a+b);
                        set[i].add(a-b);
                        set[i].add(a*b);
                        if(b!=0) set[i].add(a/b);
                        if(a!=0) set[i].add(b/a);
                    }
                }
            }
            
            if(set[i].contains(number)){
                answer = i;
                return answer;
            }
        }
    
        answer = -1;
        
        return answer;
    }
}