[프로그래머스] N으로 표현

monshell·2021년 7월 15일
0

ALGORITHM

목록 보기
2/17

문제 링크

문제 요약

  • 숫자 N과 사칙연산 기호만을 이용해서 특정 number를 만드는 방법 중 N 사용횟수의 최솟값을 구한다.

풀이 흐름

  • 첫 접근 방법 :
    접근도 못함.. 그냥 5을 1개 쓰면 5, 2개 쓰면 55, 5+5, 5-5, 5x5, 5/5 . 여기까지만 생각하고 그래서 어쩌라는거지..? 했었다.
  • 두 번째 접근 방법 :
    구글링 결과. 5을 1개 쓰면 5, 2개 쓰면 55, 5+5, 5-5, 5x5, 5/5 .
    5를 3개 쓰면
    555,
    5+55, 5-55, 5x55, 5/55,
    5+5+5, 5+5-1, 5+5x5, 5+5/5,
    5-5+5, 5-5-5, 5-5x5, 5-5/5,
    .....

  • 잘 들여다보면 5를 3개 사용한 조합의 형태는 5+(5 2개로 만든 조합), 5-(5 2개로 만든 조합), ... 이렇게 생겼다.
    -> 따라서 5를 3개 쓴 결과는 "5를 1개 쓴 조합"과 "5를 2개 쓴 조합" 의 조합. 간단하게 5의 사용 갯수를 기준으로 조합 식을 적어보면 아래와 같다.
    3 = 1+2 = 2+1
    4 = 1+3 = 2+2 = 3+1
    5 = 1+4 = 2+3 = 3+2 = 4+1

  • 이 중 덧셈, 곱셉 조합의 경우 1+2, 2+1 의 결과는 같고, 뺄셈, 나눗셈의 결과는 다르다.
    -> n개의 숫자를 사용한 조합은 "1개 조합" & "n/2개 조합", "2개 조합"&"n/2+1개 조합", ... 을 모두 합치면 된다.
    (대신 계산할 때 역순 계산 결과가 달라지는 뺄셈, 나눗셈 계산을 추가.)

  • ==> [op1+op2], [op1-op2], [op2-op1], [op1*op2], [op1/op2], [op2/op1]. 총 6가지 식을 계산하면 된다.


코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int getContinueNum(int N, int used_count)
{
	int num = 0;
	for (int i = 1; i <= used_count; i++)
		num = num * 10 + N;
	return num;
}
vector<int> getNewComb(vector<int> left, vector<int> right)
{
	vector<int> result;
	for (int i = 0; i < left.size(); i++)
	{
		for (int j = 0; j < right.size(); j++)
		{
			int op1 = left.at(i);
			int op2 = right.at(j);

			result.push_back(op1 + op2);
			result.push_back(op1 - op2);
			result.push_back(op2 - op1);
			result.push_back(op1 * op2);

			if(op2 != 0)
				result.push_back(op1 / op2);
			if(op1 != 0)
				result.push_back(op2 / op1);
		}
	}
	return result;
}
int solution(int N, int number)
{
    vector<vector<int>> all_comb = { {0}, };
	for (int used_count = 1; used_count < 9; used_count++)
	{
		int cont_num = getContinueNum(N, used_count);	// N을 연달아 사용한 수
		if (cont_num == number)
			return used_count;

		vector<int> this_comb;			// N을 used_count번 사용해서 만들 수 있는 모든 조합
		this_comb.push_back(cont_num);

		for (int i = 1; i <= used_count / 2; i++)
		{
			int j = used_count - i;
			vector<int> newcomb = getNewComb(all_comb[i], all_comb[j]);

			auto it = find(newcomb.begin(), newcomb.end(), number);
			if (it != newcomb.end())
				return used_count;
			else
				this_comb.insert(this_comb.end(), newcomb.begin(), newcomb.end());
		}
		all_comb.push_back(this_comb);
	}
	return -1;
}

0개의 댓글