N으로 표현

문제 정보

• 프로그래머스 Lv.3
• DP
• 문제 링크

풀이

N과 사칙연산만을 사용해 number를 만들 때, N의 최소 사용 횟수를 구하는 문제다.

dp를 사용하는 문제로, N을 i번 사용해서 만들 수 있는 수를 단계적으로 구해나간다. dp[i]에 number가 처음 등장하는 순간의 i가 답이다. (단, 문제 조건에 따라 i > 8인 경우 -1 반환)

또한 N을 i번 사용해서 만들 수 있는 수가 여러 개이고, 같은 수가 여러 경로로 만들어질 수 있으므로, dp[i]에는 HashSet<Integer>을 사용한다.

dp[i]를 구할 때는 두 가지 경우를 고려한다.

1. N을 i번 이어붙인 수
2. i = j + (i - j)로 분할해 사칙연산
   • N을 i번 사용하는 경우를 ‘j번 사용한 결과’와 ‘i - j번 사용한 결과’의 사칙 연산으로 나타낼 수 있다.
   • 예를 들어 dp[4]를 구할 때,
     • dp[1] & dp[3]
     • dp[2] & dp[2]
     • dp[3] & dp[1]
     • 의 모든 경우의 사칙 연산 결과를 dp[4]에 추가한다.

코드

import java.util.*;
 
class Solution {
    public int solution(int N, int number) {
        if (N == number) return 1;
        
        List<Set<Integer>> dp = new ArrayList<>();
        
        for (int i = 0; i <= 8; i++)
            dp.add(new HashSet<>());
        
        for (int i = 1; i <= 8; i++) {
            int repeat = 0;
            for (int k = 0; k < i; k++)
                repeat = repeat * 10 + N;
            
            dp.get(i).add(repeat);
            
            for (int j = 0; j < i; j++) {
                for (int a : dp.get(j)) {
                    for (int b : dp.get(i - j)) {
                        dp.get(i).add(a + b);
                        dp.get(i).add(a - b);
                        dp.get(i).add(a * b);
                        if (b != 0)
                            dp.get(i).add(a / b);
                    }
                }
            }
            
            if (dp.get(i).contains(number))
                return i;
        }
       
        return -1;
    }
}