[PGM/Java] 42895 N으로 표현

문제

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

풀이

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        
        if (N == number) return 1;
        
        Set<Integer>[] dp = new HashSet[9]; // 8보다 크면 -1 return 하므로
        int num = 0;
        for (int i=1; i<9; i++) {
            num = 10 * num + N;
            dp[i] = new HashSet<>();
            dp[i].add(num);
        }
        
        for (int i=2; i<9; i++) {
            for (int j=1; j<i; j++) {
                for (Integer a : dp[j]) {
                    for (Integer b : dp[i-j]) {
                        dp[i].add(a+b);
                        if (a-b>0) dp[i].add(a-b);
                        dp[i].add(a*b);
                        if (b>0) dp[i].add(a/b);
                        if (a>0) dp[i].add(b/a);
                    }
                }
            }
            if (dp[i].contains(number)) {
                return i;
            }
        }
        
        return -1;
    }
}

• dp는 어떤 것을 dp로 구할 것인지를 고민해야 한다.
• 처음에는 number를 dp arr의 인덱스로 활용하여 구하려고 했다. (dp[number] = Math.min(a, b); )
  • 하다보니 dp[number]를 구하는 방법이 너무 복잡했다
• 이 문제에서는 N의 사용횟수를 인덱스로 활용하여야 한다.
• 그리고 dp[i] = dp[j] + dp[i-j] 를 이용하면 구할 수 있다.
• 점화식 아이디어는 첫 풀이에서도 떠올렸는데, i, j를 dp 인덱스로 활용하면 된다는 생각을 하지 못했다,,

배운 점

• 어떤 것을 dp로 구할지를 더 고민하자.