[C++] Programmers: 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

 

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

---

• 문제 풀이

1. N을 사용한 횟수당 표현할 수 있는 수를 vector에 담습니다.

v[i] : N을 i번 사용해서 만들 수 있는 숫자 조합

2. 숫자 조합에 number가 있는지 확인합니다.

 

횟수 = 1, N = 5 일때 가능한 숫자 조합	5
횟수 = 2	55 5+5, 5-5, 5*5, 5/5
횟수 = 3	555 (55)+5, (55)-5, (55)*5, (55)/5 (5+5)+5, (5+5)-5, (5+5)*5, (5+5)/5 ...

 

즉, 특정 횟수만큼 N을 사용한 숫자 조합은 해당 횟수를 만들수 있는 덧셈 조합의 경우의 수 끼리 사칙연산을 해주면 됩니다.

(예를 들면 N=4 일 때 v[1]과 v[3], v[2]와 v[2]끼리 사칙연산)

---

• 소스 코드

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

vector<int> v[9];

int solution(int N, int number) {

    v[1].push_back(N);

    if(N == number)
    {
        return 1;
    } 
    else
    {
        for(int k=2; k<=8; k++)
        {   
            for(int i=1; i<k; i++)
            {
                for(int j=0;j<v[i].size();j++)
                {
                    for(int l=0;l<v[k-i].size();l++)
                    {
                        int a = v[i][j];
                        int b = v[k-i][l];
                        if(a!=0 && b!=0)
                        {
                            v[k].push_back(a+b);
                            v[k].push_back(a/b);
                            v[k].push_back(a-b);
                            v[k].push_back(a*b);
                        }
                    }                 
                }
            }

            int n = 0;
            for(int i=0; i<k; i++)
            {
                n += N*pow(10,i);
            }

            v[k].push_back(n); 

            for(int i=0;i<v[k].size();i++)
            {             
                if(v[k][i] == number)
                {
                    return k;
                }
            }
        }
    }
    return -1;
}