# [Gold I] 모노디지털 표현 [문제 링크](https://www.acmicpc.net/problem/2287) ## 문제 설명 <p>몇 개의 숫자 K(K는 1, 2, …, 9중 하나)와 사칙 연산(덧셈, 뺄셈, 곱셈, 나눗셈)만을 사용하여 어떤 자연수 X를 수식으로 표현한 것을 X의 K-표현이라 부른다. 수식에는 괄호가 포함될 수 있으며, 나눗셈은 나눈 몫만을 취한다.</p> <p>예를 들어 12의 5-표현을 몇 개 써 보면 5+5+(5/5)+(5/5), 55/5+5/5, (55+5)/5 등이 있다. K-표현의 길이를 사용한 K의 개수라 하면, 각각의 길이는 6, 5, 4가 된다.</p> <p>K가 주어졌을 때, 어떤 자연수의 K-표현 중 가장 짧은 길이를 알아보려 한다.</p> ## 입력 <p>첫째 줄에 K가 주어진다. 다음 줄에는 표현 식을 찾을 수의 개수 n(1 ≤ n ≤ 1,000)이 주어진다. 다음 줄에는 K-표현 중 가장 짧은 길이를 알아보려 하는 자연수 a(1 ≤ a ≤ 32,000)가 주어진다.</p> ## 출력 <p>입력되는 순서대로 K-표현의 최소 길이를 n개의 줄에 출력한다. 만약 K-표현의 최소 길이가 8보다 크다면 “NO"를 출력한다.</p> ## 풀이 1~8의 깊이에서 등장하는 모든 수들을 set에 저장하면서 완전 탐색으로 미리 전부 구해놓고 확인하면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; int k, t; vector<unordered_set<int>> dp(9); // dp[i] : k를 i번 사용하여 만들 수 있는 수들 string chk(int n) { for(int i=1;i<=8;i++) { if(dp[i].count(n)) return to_string(i); } return "NO"; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> k >> t; int last=0; for(int i=1;i<=8;i++) { last = last*10+k; dp[i].insert(last); } for(int i=1;i<8;i++) { for(int j=1;j<=i;j++) { if(i+j>8) continue; for(int a : dp[i]) { for(int b : dp[j]) { dp[i+j].insert(a+b); dp[i+j].insert(a-b); dp[i+j].insert(b-a); dp[i+j].insert(a*b); if(b!=0) dp[i+j].insert(a/b); if(a!=0) dp[i+j].insert(b/a); } } } } while(t--) { int n; cin >> n; cout << chk(n) << '\n'; } } ```