백준 2287 모노디지털 풀이

문제

https://www.acmicpc.net/problem/2287

&Title
2287번 - 모노디지털 다름

&Question
몇 개의 숫자 K(K는 1, 2, …, 9중 
하나)와 사칙 연산(덧셈, 뺄셈, 곱셈, 나눗셈)만을 사용하여 어떤 자연수 
X를 수식으로 표현한 것을 X의 K-표현이라 부른다. 수식에는 괄호가 
포함될 수 있으며, 나눗셈은 나눈 몫만을 취한다.예를 들어 12의 
5-표현을 몇 개 써 보면 5+5+(5/5)+(5/5), 55/5+5/5, (55+5)/5 등이 
있다. K-표현의 길이를 사용한 K의 개수라 하면, 각각의 길이는 
6, 5, 4가 된다.K가 주어졌을 때, 어떤 자연수의 K-표현 
중 가장 짧은 길이를 알아보려 한다. 

&Input
첫째 줄에 K가 주어진다. 다음 줄에는 표현 식을 
찾을 수의 개수 n(1≤n≤1,000)이 주어진다. 다음 줄에는 K-표현 중 
가장 짧은 길이를 알아보려 하는 자연수 a(1≤a≤32,000)가 주어진다. 

&Output
입력되는 순서대로 K-표현의 최소 길이를 n개의 줄에 출력한다. 
만약 K-표현의 최소 길이가 8보다 크다면 “NO"를 출력한다. 

&Example
-input
5
2
12
31168

-output
4
NO

요약

• 1~9사이인 숫자를 이용해 사칙연산으로 표현 했을때 K-표현이라한다.
• 어떤 자연수를 K-표현으로 나타낼때 가장 짧은 길이를 구해라

접근

• 먼저 최소 K-표현수 길이가 8보다 크면 NO이기 때문에 int 범위내로 풀 수 있다.
• set을 이용해 K-표현이 1~8자리일때를 중복제거하며 삽입해준다.

풀이

1. K-표현 연속하는 경우 (ex) 5, 55, 555, 5555 ..) 를 미리 넣어줌

    // K-표현 중 연속하게 K를 붙이는 경우를 먼저 넣어줌
    int num = 0;
    for (int i = 1; i <= 8; ++i) {
        num = 10 * num + k;
        us[i].insert(num);
    }
   

2. 각 연산을 I번째, J번째의 조합을 통해 한다. 최소인 8이 넘어가면 안된다.

    for (int i = 1; i <= 8; ++i) {
        for (int j = 1; j <= i; ++j) {
            kind = i + j;
            if (kind > 8)continue;
   

3. 각 K-표현 구한 값들에 사칙연산을 적용한다.
   1. - 할때 같은 경우 연산안하는 이유는 0이 들어가지 않게 하기위해서이다.(나눗셈시 0이 밑이면 오류, K-표현식은 자연수임)
   2. / 할때 같은 경우 큰쪽이 분자, 작은쪽이 분모로 들어가게함(이거도 반대의 경우 무조건 0이기 때문)

       for (int y : us[i]) {
       for (int x : us[j]) {
           us[kind].insert(y + x);
           if(y != x)
               us[kind].insert(abs(y - x));
           us[kind].insert(y * x);
           if (y > x)
               us[kind].insert(y / x);
           else
               us[kind].insert(x / y);
       }
       }
      

4. 이제 미리 구한 값을 통해 일치 하는 값 중 최소 K표현이 있는지 확인해주면 된다.

    // 구한것 중 일치하는 K-표현 최소길이 구하기
    int res = -1;
    for (int i = 1; i <= 8; ++i) {
        if (us[i].count(a)) {
            res = i;
            break;
        }
    }
    if (res == -1) {
        cout << "NO\n";
    }
    else {
        cout << res << '\n';
    }
   

소스

#include <iostream>
#include <unordered_set>
#include <cmath>
using namespace std;

int k, t, a;
unordered_set<int> us[9];

int main() {
	cin >> k;

	// K-표현 중 연속하게 K를 붙이는 경우를 먼저 넣어줌
	int num = 0;
	for (int i = 1; i <= 8; ++i) {
		num = 10 * num + k;
		us[i].insert(num);
	}
	int kind;
	for (int i = 1; i <= 8; ++i) {
		for (int j = 1; j <= i; ++j) {
			kind = i + j;
			if (kind > 8)continue;
			for (int y : us[i]) {
				for (int x : us[j]) {
					us[kind].insert(y + x);
					if(y != x)
						us[kind].insert(abs(y - x));
					us[kind].insert(y * x);
					if (y > x)
						us[kind].insert(y / x);
					else
						us[kind].insert(x / y);
				}
			}
		}
	}
	cin >> t;
	while (t--) {
		cin >> a;

		// 구한것 중 일치하는 K-표현 최소길이 구하기
		int res = -1;
		for (int i = 1; i <= 8; ++i) {
			if (us[i].count(a)) {
				res = i;
				break;
			}
		}
		if (res == -1) {
			cout << "NO\n";
		}
		else {
			cout << res << '\n';
		}
	}
}