프로그래머스_N으로 표현(C++)

 

https://programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

[문제 풀이]

DP를 이용하여 문제를 풀었습니다.

 

set을 선언하여 나올수 있는 경우를 메모제이션을 해주었습니다. 1 ~ 8 까지 반복문을 통해 돌면서 i가 나올 수 n_set[j],  n_set[i - j]을 이용하여 사칙연산 계산을 해주었습니다.

[코드]

#include <string>
#include <vector>
#include<set>

using namespace std;

set<int> n_set[9];

int solution(int N, int number) {
	int answer = 1;
	int ten = 10;
	int temp = N;

	n_set[1].insert(N);

	if (N == number)
		return answer;

	for (int i = 2; i < 9; i++) {
		answer++;

		temp = temp + N * ten;

		for (int j = 1; j < i; j++) {

			for (auto jtem : n_set[j]) {
				for (auto ktem : n_set[i - j]) {


					n_set[i].insert(jtem + ktem);

					n_set[i].insert(jtem * ktem);

					n_set[i].insert(jtem - ktem);

					if (ktem != 0)
						n_set[i].insert(jtem / ktem);

				}
			}

		}

		n_set[i].insert(temp);
		ten *= 10;

		if (n_set[i].count(number) > 0) {
			return answer;
		}
	}

	return -1;
}