[프로그래머스/알고리즘] N으로 표현

N으로 표현

입출력 예

N : 5

number : 12

return : 4

해결 방법

제가 푼 방법은 N 2개 가지고 가능한 모든 수를 구하고 

n이 3개를 이용한 값을 만들기 위해서

n이 2개 사용한 값과 n이 하나인 모든 값을 n이 3개인 값의 배열에 저장합니다(1개 X 2개 , 2개 X 1개)

n이 4개를 이용한 값을 만들기 위해서

1개X3개 2개X2개 3개X1개 배열들의 모든 값들을 n이 4개인 배열에 저장합니다.

이런 방법으로 문제를 풀면 정답이 나왔습니다.

당연히 n이 많을 수록 나오는 값이 굉장히 불어납니다. 그래서 효율은 많이 떨어지는 코드입니다.

소스 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int func1(int number)
{
	int count = 10;
	for (int i = 0; i < 10; i++)
	{
		if (number / 10 == 0)
			return count;
		else count * 10;
	}
}

int solution(int N, int number) {
    int answer = 0;
    vector<int> a[9];  
    if(number==N)
        return 1;
    a[1].push_back(N);
   	for (int i = 2; i<9; i++)        //8번 실행
	{
        if((N * func1(a[i-1][0])) + N==number) return i;      //n nn nnn nnnn 만들기
        else a[i].push_back((N * func1(a[i][0])) + N);
		for (int j = 1; j<i; j++)    //연산 갯수
		{
			for (int k = 0; k<a[j].size(); k++)
			{
				for (int p = 0; p<a[i - j].size(); p++)
				{
					if (a[j][k] * a[i - j][p] == number) return i;
							a[i].push_back(a[j][k] * a[i - j][p]);
				
					if (a[j][k] + a[i - j][p] == number) return i;
							a[i].push_back(a[j][k] + a[i - j][p]);
			
					if (a[j][k] - a[i - j][p] == number) return i;
						a[i].push_back(a[j][k] - a[i - j][p]);
					if (a[i - j][p]!= 0) {  //0으로 못나눔
						if (a[j][k] / a[i - j][p] == number) return i;
						else if (a[j][k] / a[i - j][p] == 0);
						else a[i].push_back(a[j][k] / a[i - j][p]);				
					}
				}
			}
		}
    }
    return -1;
}

근대 이게 왜 level1인가요?