[프로그래머스 문제풀이] 31. N으로 표현

동적계획법이란?

코드를 풀기 전 먼저 동적계획법에 대해서 알아보았다. 동적계획법이란 간단하게 말하면 이전 과정에서 사용한 풀이를 재활용해서 푸는 것을 말한다. 과정을 계속 저장하는 풀이 방법이다.

코드 설명

N 1개의 계산식부터 8개의 식까지 탐색해야 하는데 dp벡터에 결과를 저장해 놓고
N의 개수가 늘어날 때마다 이전 개수의 계산식의 결과들을 재활용한다.

🎉완성코드

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

using namespace std;

int make_number(const int& N, const int& count) {
	string num = "";
	for (int i = 0; i < count; ++i)
		num += to_string(N);
	return stoi(num);
}
int solution(int N, int number) {
	//N마다 
	vector<int>dp[9];

	// N 1개
	dp[1].push_back(make_number(N, 1));
	if (number == N)
		return 1;

	// N 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;
				for (auto& k : dp[x - i])
				{
					if (k == 0)		continue;

					//(j 연산 k) 계산하고 넣기 -> 계산에서 N의 개수는 x개
					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;
	}

	// N 9개
	return -1;
}

N으로 표현 문제 링크