[JAVA / 자바] Lv.3_N으로 표현

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

프로그래머스

---

import java.util.*;
class Solution {

    public int solution(int N, int number) {
        int answer = -1;
        Set<Integer>[] dp = new Set[9];
        int tmp = N;
        for (int i = 1; i < 9; i++) {
            dp[i] = new HashSet<>();
            if(tmp == number){
                answer = i;
                break;
            }
            dp[i].add(tmp);
            tmp = tmp * 10 + N;
        }
        if(answer == -1) {
            for (int i = 2; i < 9; i++) {
                if (getUseCnt(i, number, dp)) {
                    answer = i;
                    break;
                }
            }
        }
        return answer;
    }

    private boolean getUseCnt(int num, int number, Set<Integer>[] dp) {
        for (int n1 = 1; n1 < num ; n1++) {
            int n2 = num - n1;
            if(n1 == n2) { //같은 경우엔 -, / 가 중복되므로 순서 바꿔서 한번 더 X
                for (int i : dp[n1]) {
                    for (int j : dp[n2]) {
                        dp[num].add(i + j);
                        dp[num].add(i * j);
                        dp[num].add(i - j);
                        if(j != 0)
                            dp[num].add(i / j);
                        if(dp[num].contains(number)) return true;
                    }
                }
            }else {
                for (int i : dp[n1]) {
                    for (int j : dp[n2]) {
                        dp[num].add(i + j);
                        dp[num].add(i * j);
                        dp[num].add(i - j);
                        dp[num].add(j - i);
                        if(j != 0) //0으로 나누는 것 주의
                            dp[num].add(i / j);
                        if(i != 0)
                            dp[num].add(j / i);
                        if(dp[num].contains(number)) return true;
                    }
                }
            }
        }
        return false;
    }
}

💡 DP

풀이

- dp를 활용해 풀이. 이때 dp[i] = N을 i개 사용해서 만들 수 있는 모든 경우의 숫자

- i개의 숫자를 사용해 number에 해당하는 값을 만들 수 있는지가 관건이므로 n개를 같은 수만큼 사용한 결과물들은 중복 제거를 해줌 (결과가 중요한 것이므로 구분을 해줄 필요가 없음)

- 예외처리

   (1) N = number 인 경우 

   (2) NN... = number인 경우

   → set에 값 세팅해 줄 때 검사 후 처리

- dp[5] 의 경우 N을 5개 사용해 만들 수 있는 수

   - N * 1개 , 4개인 수의 조합 & 2개, 3개인 수의 조합 ⊂ N * 5개로 만들 수 있는 수

   - 이때 가능한 조합은 사칙연산, 즉 4가지 (+, -, /, *)

   - 단, a - b != b - a 이므로 dp[1] - dp[4] , dp[4] - dp[1]을 각각 계산해줘야 함

- 조합 구현은 이중 for문으로 함