[백준] 10421 : 수식 완성하기

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

10421번: 수식 완성하기

---

• 첫번째 숫자는 최대 5자리, 두번째 숫자는 최대 3자리이고, 각 자릿수마다 가능한 값은 1~9 까지 최대 9개가 있다.
• 따라서 모든 숫자에 대한 경우의 수도 최대 9^8 가지가 있으므로, 전부 탐색을 해서 유효한지 검사해줄 수 있다.
• 각 숫자마다 백트래킹을 통해 자릿수를 하나씩 뽑아가며 모든 경우의 수를 확인한다.
• 21.7.23 현재 BOJ 의 입력 데이터 형식에 문제가 있다고 보여진다.
• 문제의 설명에서는 총 4줄에 걸쳐 값들이 들어오는데, 입력 데이터 중 그 형식을 지키지 않는 것들이 존재한다. (참고) https://www.acmicpc.net/board/view/69371
• 실제로 동일한 로직의 파이썬 코드를 제출할 시, input 에서 입력을 받지 못해 EOFError 가 발생한다.

---

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int N, K, answer, tmp;
int digits[7];
int numbers[10];

// 특정 위치의 값이 주어지면 수식을 완성시킬 수 있는 값인지 검사
bool is_valid(string tmp, int idx)
{
    // 해당 값의 자릿수가 수식의 자릿수와 같은지
    if(tmp.size() != digits[idx]) return false;
    // 해당 값이 모두 주어진 값들로만 구성이 되어있는지
    for(int i = 0 ; i < tmp.size() ; i++)
    {
        bool exist = false;
        for(int k = 0 ; k < K ; k++)
        {
            if((tmp[i]-'0')==numbers[k]) exist = true;
        }
        if(!exist) return false;
    }
    return true;
}

// 두 숫자가 주어졌을 때, 현재 수식을 만족하는지 검사
bool able(int a, int b)
{
    // 두 숫자를 곱한 정답이 유효한지
    if(!is_valid(to_string(a * b), N-1)) return false;
    // 첫번째 숫자와, 두번째 숫자의 각 자릿수들을 곱한 중간값들이 유효한지
    for(int i = 0 ; i < digits[1] ; i++)
    {
        if(!is_valid(to_string(a * (to_string(b)[i]-'0')), N-2-i)) return false;
    }
    return true;
}

// 두번째 숫자(최대 3자리) 백트래킹으로 가능한 모든 경우의 수 탐색
void selectB(int blen, int bval, int aval)
{
    // 두번째 숫자도 다 뽑았으면, 첫번째 숫자와 함께 수식을 완성시킬 수 있는지 검사
    if(blen == digits[1])
    {
        answer += able(aval, bval);
        return;
    }
    // 1의자리부터 하나씩 뽑아나감
    for(int i = 0 ; i < K ; i++)
    {
        selectB(blen+1, bval+(numbers[i])*(pow(10,blen)), aval);
    }
}

// 첫번째 숫자(최대 5자리) 백트래킹으로 가능한 모든 경우의 수 탐색
void selectA(int alen, int aval)
{
    // 첫번째 숫자를 다 뽑았으면, 두번째 숫자를 뽑기 시작
    if(alen == digits[0])  
    {
        selectB(0, 0, aval);
        return;
    }
    // 1의자리부터 하나씩 뽑아나감
    for(int i = 0 ; i < K ; i++)
    {
        selectA(alen+1, aval+(numbers[i])*(pow(10,alen)));
    }
}

int main(void)
{
    cin >> N;
    for(int i = 0 ; i < N ; i++)
    {
        cin >> tmp;
        digits[i] = tmp;
    }
    cin >> K;
    for(int i = 0 ; i < K ; i++)
    {
        cin >> tmp;
        numbers[i] = tmp;
    }

    selectA(0, 0);
    cout << answer << endl;    
}