N으로 표현 (feat. 프로그래머스, 42895번)

N으로 표현
https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

 

반응형

 

// woohyeon.kim
// https://school.programmers.co.kr/learn/courses/30/lessons/42895
#include <vector>
#include <cmath>
using namespace std;
int make_number(const int& N, const int& count) {
	int ret = 0;
	for (int i = 0; i < count; ++i)
		ret += N * pow(10, i);
	return ret;
}
int solution(int N, int number) {
	vector<int>dp[9];
	// 1자릿수
	dp[1].push_back(make_number(N, 1));
	for (int i = 0; i < dp[1].size(); ++i)
		if (number == dp[1][i])
			return 1;
	// 2자릿수 ~ 8자릿수
	for (int x = 2; x <= 8; ++x) {
		dp[x].push_back(make_number(N, x));
		for (int i = 1; i < x; ++i)
			for (auto& j : dp[i]) {
				if (j == 0)			continue;	// 0인 경우, 계산에 의미가 없음 (나눗셈 연산 문제 포함)
				for (auto& k : dp[x - i])
				{
					if (k == 0)		continue;	// 0인 경우, 계산에 의미가 없음 (나눗셈 연산 문제 포함)
					dp[x].push_back(j * k), dp[x].push_back(j / k), dp[x].push_back(j + k), dp[x].push_back(j - k);
				}
			}
		for (int i = 0; i < dp[x].size(); ++i)
			if (number == dp[x][i])
				return x;
	}
	// 9자릿수 이상
	return -1;
}
// *&)*@*

 

1. 예제의 5,12를 예로 들어보겠습니다.
2. N=1인 경우, 5밖에 없습니다.
3. N=2인 경우, 55와 N(1)-N(1)간 사칙연산이 있습니다.
4. N=3인 경우, 555와 N(1)-N(2)간 N(2)-N(1)간 사칙연산이 있습니다.
5. 따라서 N(n) = N(1)-N(n-1)간 사칙연산 + N(2)-N(n-2)간 사칙연산 + ... + N(n-1)-N(1)간 사칙연산 이라는 식이 도출됩니다.