문제

Programmers Lv3, N으로 표현

핵심

• 숫자 N이 주어지고, 최대 8번 사용해서 number 숫자를 만들어야 한다. +, -, *, /와 괄호를 사용할 수 있다. 문제 예시를 보면 사칙연산 외에도 문자열을 붙여주는 경우를 고려해야 한다.
• 단순히 사칙연산, 문자열 이어 붙이기라면 +, -, *, /, 이어 붙이기로 순열을 만들어낼 수 있겠지만 괄호가 임의의 위치에 생겨 결괏값을 변경할 수 있다. 이 문제는 괄호 처리가 핵심이다.
• 먼저 규칙을 찾기 위해 5를 사용해서 만들 수 있는 수를 나열해 보자.

- 5을 1개 사용할 때 
{5}

- 5를 2개 사용할 때 
{55}, {5+5}, {5-5}, {5*5}, {5/5}

- 5를 3개 사용할 때 -> 
{555},
{5+55}, {5-55}, {5*55}, {5/55}
{5+(5+5)}, {5-(5+5)}, {5*(5+5)}, {5/(5+5)}
{5+(5-5)}, {5-(5-5)}, {5*(5-5)}
{5+(5*5)}, {5-(5*5)}, {5*(5*5)}, {5/(5*5)}
{5+(5/5)}, {5-(5/5)}, {5*(5/5)}, {5/(5/5)}
...

• 가만 보면 규칙을 찾을 수 있다. 괄호 처리를 한 경우의 수는 5를 1개 사용할 때와 5를 2개 사용할 때 경우를 구한 뒤 사칙연산을 한 결과이다.
• 그런데 놓친 케이스는 없을까? 위에 케이스는 앞에 괄호를 고려하지 못한다. 5를 2개 사용할 때와 5를 1개 사용할 때 경우를 더하면 괄호가 앞에 있는 경우도 고려할 수 있다.

{555},
{55+5}, {5-55}, {5*55}, {5/55}
{(5+5)+5)}, {(5+5)-5}, {(5+5)*5}, {(5+5)/5}
{(5-5)+5}, {(5-5)-5}, {(5-5)*5}
{(5*5)+5}, {(5*5)-5}, {(5*5)*5}, {(5*5)/5}
{(5/5)+5}, {(5/5)-5}, {(5/5)*5}, {(5/5)/5}

• 이렇게 5를 3개 사용할 때 모든 경우를 구할 수 있다. 그럼 5를 4개 구할 때는?

5를 1개 쓴 것과 5를 3개 쓴 것의 사칙연산
5를 2개 쓴 것과 5를 2개 쓴 것의 사칙연산
5를 3개 쓴 것과 5를 1개 쓴 것의 사칙연산

• dp[i] = X;를 N을 i번 쓰면 만들 수 있는 수라고 했을 때 지금까지의 과정을 코드로 표현하면 아래와 같다.

dp.get(1).add(N); // 처음에 5를 넣어준다.
for (int i = 1; i <= 8; ++i) { // 최대 8번 반복한다.
	
	dp.get(i).add(Integer.parseInt((String.valueOf(N).repeat(i)))); // 5, 55, 555 같은 이어 붙여주는 숫자를 만들어주기 위함
    
	for (int j = 1; j < i; ++j) {
		for (var a : dp.get(j)) {
			for (var 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; // N을 i번 쓴 값에 number가 있다면 최솟값을 찾은 것이므로 i를 반환한다.
}
return -1;

개선

시간복잡도

• $O(7*4^8)$

코드

import java.util.*;

class Solution {
    public int solution(int N, int number) {
                
        List<Set<Integer>> dp = new ArrayList<>();
        
        for (int i = 0; i <= 8; ++i)
            dp.add(new HashSet<>());
        
        dp.get(1).add(N);
        
        for (int i = 1; i <= 8; ++i) {
            
            dp.get(i).add(Integer.parseInt((String.valueOf(N).repeat(i))));
            
            for (int j = 1; j < i; ++j) {
                for (var a : dp.get(j)) {
                    for (var 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;
    }
}