[백준/BOJ] 백준 2287번 : 모노디지털 표현

www.acmicpc.net/problem/2287

2287번: 모노디지털 표현

result[길이]에 각각의 길이에 만들어질 수 있는 값을 구한다. 우선 연산자 없이 k로만 이루어진 각 길이의 값을 저장해 놓고 구한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <cmath>
using namespace std;

int k;
int n;
set<int> result[9]; //각 길이의 결과를 저장한다
set<int>::iterator it1;
set<int>::iterator it2;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> k;
	cin >> n;

	int temp = k;
	for (int i = 1; i <= 8; i++)
	{
		result[i].insert(temp); //연산자 없이 k로만 이루어진 각 길이의 값을 저장한다

		temp = temp * 10 + k;
	}

	//각각의 길이에 만들어질 수 있는 값을 구한다
	for (int i = 1; i <= 8; i++)
		for (int j = 1; j <= i; j++)
		{

			if (i + j <= 8) //최소 길이가 8이하인것만 구한다
			{
				for (it1 = result[i].begin(); it1 != result[i].end(); it1++)
					for (it2 = result[j].begin(); it2 != result[j].end(); it2++)
					{
						//더하기
						temp = (*it1) + (*it2);
						result[i + j].insert(temp);

						//빼기 (0이 되는것 제외)
						temp = (*it1) - (*it2);
						if (temp != 0)
						{
							result[i + j].insert(temp);
						}
						temp = (*it2) - (*it1);
						if (temp != 0)
						{
							result[i + j].insert(temp);
						}

						//곱하기
						temp = (*it1) * (*it2);
						result[i + j].insert(temp);

						//나누기 (0이 되는것 제외)
						if ((*it2) != 0 && (*it1) > (*it2))
						{
							temp = (*it1) / (*it2);
							result[i + j].insert(temp);
						}
						else if ((*it1) != 0 && (*it1) <= (*it2))
						{
							temp = (*it2) / (*it1);
							result[i + j].insert(temp);
						}
					}
			}
		}

	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;

		bool check = false;
		int check_num;
		for (int j = 1; j <= 8; j++)
		{
			for (it1 = result[j].begin(); it1 != result[j].end(); it1++)
			{
				if ((*it1) == a) //a를 발견 했을때
				{ 
					check = true;
					check_num = j;

					break;
				}
			}

			if (check == true)
				break;
		}

		if (check == false)
			cout << "NO" << "\n";
		else
			cout << check_num << "\n";
	}

	return 0;
}