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

N으로 표현 문제보기

N과 number가 주어지면, 최소한의 갯수의 N으로 number를 만드는 문제
예를 들어, N = 5, number = 12 일때
12 = (55 + 5) / 5 이므로, 4개의 5로 12를 표현 할 수 있다.

---

문제풀이

set을 이용한 DP 문제로 풀 수 있다.
최대 8개의 N만 사용 가능하므로, 8개의 set을 만들고
i번째 set은 i개의 N을 사용했을 때 만들 수 있는 모든 수를 가진다.

i번째 set에 들어갈 수 있는 숫자는

• N을 i개 붙여서 만든 숫자 (예를 들어 N=5, i=7일때 5555555)
• 1번째 set과 i-1번째 set에 들어가는 숫자들 각각 끼리의 사칙연산
• 2번째 set과 i-2번째 set에 ..
  ...
• i/2번째 set과 i-(i/2)번째 set에 들어가는 숫자들 각각 끼리의 사칙연산

따라서 N을 i개 붙여서 만든 숫자를 미리 넣어주고
다른 숫자들은 DP로, 1번째 set부터 구해 나가면서 채워 넣으면 된다.

i번째 set을 구한 후, set에 number가 있으면 i를 return
8번째 set까지 구하고 number를 찾지 못하면 -1을 return

C++에서 set을 사용하여 문제를 풀고 나서 생각해보니 데이터를 정렬할 필요가 없어서
unordered set로 바꾸었더니 실행속도가 매우 빨라졌다.
unordered 컨테이너는 hash를 사용하여 자료를 저장하기 때문에, 메모리가 조금 더 들지만 속도 측면에서는 매우 유리한듯

---

C++ Code

#include<iostream>
#include <unordered_set>
#include <cmath>
using namespace std;

void fill(int x, int number);
void operate(int x, int a, int b);

unordered_set<int> s[9];
unordered_set<int>::iterator iter1, iter2;

int solution(int N, int number) {
    int basic_num;
    for(int i=1; i<9; i++){
        basic_num=0;
        for(int j=0; j<i; j++){
            basic_num+= N*pow(10,j);
        }
        s[i].insert(basic_num);    
    }

    for(int i=2; i<9; i++){
        fill(i, number);
        if(s[i].find(number) != s[i].end()) return i;
    }

    return -1;
}

void fill(int x, int number){
    for(int i=1; i<=x/2; i++){
        operate(x, i, x-i);
    }
}

void operate(int x, int a, int b){
    int num1, num2;
    for (iter1 = s[a].begin(); iter1 != s[a].end(); ++iter1){
        num1 = *iter1;
        for (iter2 = s[b].begin(); iter2 != s[b].end(); ++iter2){
            num2 = *iter2;

            s[x].insert(num1+num2);
            s[x].insert(num1-num2);
            s[x].insert(num2-num1);
            s[x].insert(num1*num2);
            if(num2!=0) s[x].insert(num1/num2);
            if(num1!=0) s[x].insert(num2/num1);
        }
    }
}

Python Code

s = [ set()for i in range(9) ]
def solution(N, number):
    for i in range(9):
        basic_num = 0;
        for j in range(i):
            basic_num += N*pow(10,j)
        s[i].add(basic_num)


    for i in range(2,9):
        fill(i,number)
        if(number in s[i]):
            return i

    for j in range(9):
        print(s[j])

    return -1

def fill(x, number):
    for i in range(1,x//2+1):
        operate(x,i,x-i)

def operate(x, a, b):
    for num1 in s[a]:
        for num2 in s[b]:
            s[x].add(num1+num2)
            s[x].add(num1-num2)
            s[x].add(num2-num1)
            s[x].add(num1*num2)
            if(num2!=0):
                s[x].add(num1//num2)
            if(num1!=0):
                s[x].add(num2//num1)