[프로그래머스/C++] N으로 표현

[프로그래머스/C++] N으로 표현

1. 문제

아래와 같이 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 함수를 작성하세요.

2. 제한사항

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

3. 풀이

• 예를 들어 4개의 N을 이용해서 만들 수 있는 숫자는 아래와 같다.
  • NNNN(ex. 4444)
  • (1개의 N을 이용해서 만들 수 있는 숫자) +, -, *, / (3개의 N을 이용해서 만들 수 있는 숫자)
  • (2개의 N을 이용해서 만들 수 있는 숫자) +, -, *, / (2개의 N을 이용해서 만들 수 있는 숫자)
  • (3개의 N을 이용해서 만들 수 있는 숫자) +, -, *, / (1개의 N을 이용해서 만들 수 있는 숫자)
• 모든 경우를 구해주면 된다.
• 중복된 숫자가 너무 많이 나올 것 같아서 그나마 계산을 좀 줄이려고 set 자료구조를 이용했다. 안 해도 상관없다.

4. 처음 코드와 달라진 점

• number과 현재 숫자를 비교하는 코드가 중간에 있어서 8개의 N을 사용했을 때는 확인 안 해주고 있었다. 마지막에 추가했다.
• 예전에 푼 적이 있는 문제라서 마지막에 확인했는데 아주 지저분했다.

5. 코드 (예전 풀이)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> v[9];

int make_n(int N, int len){
    int result = N;
    for(int i =1; i<len; ++i){
        result *= 10;
        result += N;
    }
    return result;
}

int solution(int N, int number) {
    int answer = -1;
    for(int i=1; i<9; ++i){
        v[i].push_back(make_n(N, i));
    }

    bool is_found = false;
    for(int i=2; i<9; ++i){
        if(is_found) break;
        for(int j=1; j<i; ++j){
            if(is_found) break;
            for(int k=0; k<v[j].size(); ++k){
                if(is_found) break;
                int first = v[j][k];
                if(first == number) {
                    answer = j;
                    is_found = true;
                    break;
                }
                for(int l=0; l<v[i-j].size(); ++l){
                    int second = v[i-j][l];
                    if(second == 0) continue;
                    v[i].push_back(first + second);
                    v[i].push_back(first - second);
                    v[i].push_back(first * second);
                    v[i].push_back(first / second);
                }
            }
        }
    }   
    if(!is_found){
        for(int i=0; i<v[8].size(); ++i){
            if(v[8][i] == number){
                answer = 8;
                break;
            }
        }    
    }
    
    return answer;
}

6. 코드 (21.09.05)

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>

using namespace std;

set<int> arr[9];

int makeNewN(int n, int count) {
    int result = n;
    for (int i = 1; i < count; ++i) {
        result *= 10;
        result += n;
    }
    return result;
}

int solution(int N, int number) {
    int answer = -1;
    for (int i = 1; i < 9; ++i) {
        int newN = makeNewN(N, i);
        if (newN == number) return i;
        arr[i].insert(newN);
    }
    
    for (int i = 2; i < 9; ++i) {
        for (int j = 1; j < i; ++j) {
            for (auto it = arr[j].begin(); it != arr[j].end(); ++it) {
                int a = *it;
                if (a == number) return j;
                
                for(auto itb = arr[i-j].begin(); itb != arr[i-j].end(); ++itb) {
                    int b = *itb;
                    if (a == 0 || b == 0) continue;
                    arr[i].insert(a + b);
                    arr[i].insert(a - b);
                    arr[i].insert(a * b);
                    arr[i].insert(a / b);
                }
            }
        }
    }
    for (auto it = arr[8].begin(); it != arr[8].end(); ++it) {
        if (*it == number) return 8;
    }
    
    return answer;
}