코딩 테스트 - N으로 표현

N으로 표현

문제 링크 : N으로 표현

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한 사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

풀이 방법

• 5를 예로 들어서 보았을 때, 5를 사용한 횟수를 기준으로 하나씩 늘려보자.
  • 1 -> 5
  • 2 -> 55, 5+5, 5-5, 5*5, 5/5
  • 3 -> 555, 5+55, 5-55, 55-5, 5*55, 55/5, 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*(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를 k개만큼 사용했다고 가정하면 (1, k-1), (2, k-2), ...처럼 쌍을 두고 서로 사칙연산을 통해 나올 수 있는 수를 구할 수 있다.
• 중복되지 않게 저장하기 위해 std::unordered_set 자료구조를 통해 저장을 했고, 먼저 5, 55, 555...를 저장했다.
• 이후에 저장해놨던 값들을 통해 N을 사용한 횟수별로 사칙연산을 통해 값을 계속 저장해나가면서 dp 알고리즘을 통해 문제를 풀었다.
• 주의할 점으로는 0을 나눌 수는 없기에 이 부분은 예외처리를 해야되고, 55-5와 5-55는 다르기 때문에 순서도 고려해야 한다.
  -> 이 문제 풀이의 시간복잡도는 정확하게 모르겠지만, 약 O(N^4) 정도로 기하급수적으로 매우 높을 것으로 보이지만, unordered_set을 통해서 중복 제거를 하기 때문에 충분히 통과가 가능한 것으로 보인다.

구현

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

int solution(int N, int number) {
    int answer = -1;
    
    vector<unordered_set<int>> NSets(9);
    int temp = N;
    // 5, 55, 555... 먼저 삽입
    for(int i = 1; i <= 8; i++){
        if(temp == number){
            return i;
        }
        NSets[i].insert(temp);
        temp = temp * 10 + N;
    }
    
    int plus, minus1, minus2, mult, div;
    int l, r;
    
    // 기존에 저장해놨던 값들을 통해 N을 사용한 횟수별로 사칙연산을 통해 값을 구하기
    for(int i = 2; i <= 8; i++){
        for(int j = 1; j * 2 <= i; j++){
            for(auto it1 = NSets[i - j].begin(); it1 != NSets[i - j].end(); ++it1){
                for(auto it2 = NSets[j].begin(); it2 != NSets[j].end(); ++it2){
                    l = *it1; r = *it2;
                    
                    plus = l + r; 
                    minus1 = l - r;
                    minus2 = r - l;
                    mult = l * r; 
                    
                    if (plus == number || minus1 == number
                        || minus2 == number || mult == number) return i;
                    NSets[i].insert(plus);
                    NSets[i].insert(minus1);
                    NSets[i].insert(minus2);
                    NSets[i].insert(mult);
                    
                    if(r != 0){
                        div = l / r;
                        if(div == number) return i;
                        NSets[i].insert(div);
                    }
                    if(l != 0){
                        div = r / l;
                        if(div == number) return i;
                        NSets[i].insert(div);
                    }
                }
            }
        }
    }
    
    return answer;
}