[POI] 백준 2287 - 모노디지털 표현

noj.am/2287

 

분석과 아이디어

본문에 자연수 X를 몇 개의 숫자 k와 사칙연산을 통해 표현한다고 되어있다. 설명에서 5는 1, 55는 2 임을 발견할 수 있고 숫자를 몇 개 이어 붙였는지로 표현 길이를 결정했음을 알 수 있다.

 

그러면 우리는 어떻게 표현 길이를 최소화시킬 수 있을까?

 

설명에 나열된 표현식들을 보면 중복될 수 있는 경우도 분명 있을 것이고 거기에 괄호도 고려해야 하기 때문에 상당히 어려워 보인다.

 

하지만 표현의 결과는 식도 아니고 값이다. k와 연산자들을 어떻게 섞었든 그 결과는 값으로 존재한다.

 

표현의 결과로 a와 b가 있다면 a (*, /, +, -) b 꼴로 c가 계산될 것이며, c의 표현 길이는 a를 만들기 위한 표현 길이 + b를 만들기 위한 표현 길이가 된다.

 

우리는 이렇게 계산한 표현 길이 중 최소를 찾으면 되며, 표현의 기초가 되는 수들을 저장한 후 어떤 표현으로 나타낸 수를 동적계획법으로 풀 수 있다는 생각을 할 수 있다.

 

기초가 되는 수들은 어떤 것들이 있냐고? 게시글 처음에서 언급한 이어 붙이는 수들(k, 10k + k, 100k + 10k + k,...)을 저장하고 시작하면 된다.

풀이

동적계획법으로 해결하기 위해 dp테이블은 다음과 같이 둔다.

 

dp[i] := 표현 길이 i를 가진 자연수들의 집합

 

아까 말한 이어 붙이는 수들을 저장한다. 표현 길이가 8을 넘으면 안 된다고 했으므로 8번까지 이어 붙인 수들만 저장해주자.

 

그런 다음 4 중첩 반복문을 통해 모든 표현 길이에 대해 집합을 구해주자. 각 루프의 인덱스를 i, j, k, s라 했을 때

 

표현 길이가 i인 자연수 집합의 k번째 원소와 표현 길이가 j인 자연수 집합의 s번째 원소를 사칙연산 한 값을 i + j번째 집합에 넣어주면 된다.

 

더하기와 곱하기는 그냥 넣어주면 되고 나머지에서 조금 신경을 써야 한다.

 

빼기에서는 두 원소를 뺀 결과가 0이 되면 안 된다. 음수의 처리를 놓고 의문이 들 수 있는데, 음수일 경우 두 원소의 순서를 바꾸면 양수가 되기에 절댓값을 취해주면 된다.

 

나누기에서는 그 결과가 0이 되면 안 된다. 큰 수를 작은 수로 나눌 수 있게 해주자.

 

반복문을 마치고 나면 집합의 원소가 모두 채워져 있을 것이다. 이걸 이제 쿼리에 알맞게 출력해주면 된다.

 

물론 이렇게 하면 자연수 x를 표현하는 길이가 여러 개 나올 수 있다.

 

따라서 표현 길이 1인 집합부터 오름차순으로 탐색하면서 탐색 중인 집합에 값이 있으면 그 표현 길이를 출력하고 값을 못 찾으면 NO를 출력하면 되겠다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
unordered_set<int> dp[9];
int k;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> k;
    int tmp = k;
    int cnt = 1;
 
    while (cnt < 9)
    {
        dp[cnt++].insert(tmp);
        tmp = tmp * 10 + k;
    }
 
    for (int i = 1; i < 8; ++i)
    {
        for (int j = 1; j < 8; ++j)
        {
            if (i + j > 8)
                continue;
 
            for (auto k = dp[i].begin(); k != dp[i].end(); ++k)
            {
                for (auto s = dp[j].begin(); s != dp[j].end(); ++s)
                {
                    dp[i + j].insert(*k + *s);
                    dp[i + j].insert(*k * *s);
                    if (abs(*k - *s))
                        dp[i + j].insert(abs(*k - *s));
                    dp[i + j].insert(max(*k, *s) / min(*k, *s));
                }
            }
        }
    }
 
    int n;
    cin >> n;
    
    while (n--)
    {
        int a;
        cin >> a;
        bool pass = false;
 
        for (int i = 1; i <= 8; ++i)
        {
            if (dp[i].find(a) != dp[i].end())
            {
                pass = true;
                cout << i << '\n';
                break;
            }
        }
 
        if (!pass)
            cout << "NO\n";
    }
}