[프로그래머스] N으로 표현 (c++)

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

프로그래머스

 

[문제 요약]

• 주어진 숫자 N 으로 사칙연산하여 number 를 만들 수 있는 N 의 최소 개수 구하기

 

[풀이]

• 완전 탐색 문제로, number = 10^k 일 때 O(k^k) 에 풀린다. (풀이 코드는 러프하게 O(8^8) 로 해결)
• number 이 커지면 DP로 최적화 가능하다.
• cur = (w - 1)(N * 10) + N 의 값인 { N, NN, NNN, ..., NNNNNNNN} 의 값들을 재귀적으로 사칙 연산하여 해결.

#include <cstdio>
#include <vector>
using namespace std;

int mm = 9;
vector<int> v;

void foo(int cur, int target, int cnt = 0)
{
	if (cnt >= mm)
	{
		return;
	}
	else if (cur == target)
	{
		mm = cnt;
		return;
	}
	for (int i = 0; i < v.size(); i++)
	{
		foo(cur + v[i], target, cnt + i + 1);
		foo(cur * v[i], target, cnt + i + 1);
		foo(cur / v[i], target, cnt + i + 1);
		foo(cur - v[i], target, cnt + i + 1);
	}
}

int solution(int N, int number)
{
	int answer = 0;
	int tmp = N;

	for (int i = 0; i < 8; i++)
	{
		v.push_back(tmp);
		tmp = tmp * 10 + N;
	}

	foo(0, number);

	if (mm > 8)
		mm = -1;

	return mm;
}

 

[코드 설명]

• 0 + N , 0 + N + N, 0 + N + N + ... N 을 시작으로 0 + N + N + ... NN ~ 0 - N 까지 모든 경우를 재귀적으로 연산
• N 의 개수는 cnt 로 표현되며, 최대값인 9 보다 크거나 같은 경우 그리고 최소의 N의 개수보다 큰 경우 더이상 연산하지 않는다.
• 궁금한 부분은 댓글 남겨주시면 시간 날 때 답글 달겠습니다.