백준 2731, 1379와 세제곱

개요

문제가 있는 링크
플레이 5, 정수론, 역추적
정육면체 세 개로 나눴을 때 N이 꼬리인 수 찾기

입장

1. 역추적 대신 bigInt를 구현할 수 있는지 여부에 대한 질문은 단순히 역추적 자체입니다. 문자열을 거꾸로 삽입한 후 앞에서 0부터 9까지 삽입하고 다음 단계에서 큐브의 하위 문자열이 같은지 확인합니다.할 수 있어요.
2. BigInt를 사용해야 합니까? 그렇다면 주사위에서 10자리를 굴리면 30자리가 되어 롱롱의 범위를 넘어선다. 문자열로 취급하고 10자리에서 자릅니다. 다른 방법으로 구현하신 분들도 계시는데 저는 해결 방법도 몰랐습니다.
3. 만약에 곱한 값의 n번째 자리와 목표값이 같으면 건너뛴다. 오류를 줄이려면 n번째 숫자가 0이면 곱한 값이 아직 채워지지 않은 것입니다.해야한다.
4. 즉, 예를 들어 27을 입력하면 009가 됩니다. 이렇게 하면 결과 값에 0이 붙는 경우가 있으니 잘 제거해 주세요.

의사 코드

struct BigInt {
    // 뒤집은 상태로 입력
    string v
    int length
} n, t

// pos = 현재 위치, action = 어떤 숫자를 추가했는지
recur(t, pos, action) {
    if (pos = end) 
        // 0빼고 뒤집어 출력
        print(reverse(action))
    if (t(pos) = n(pos))
        return recur(t, pos+1, action+"0")
    if (!t(pos) && n(pos)=='0')
        return recur(t, pos+1, action+"0")
    for (i = '0'~'9')
        // action에 i추가, 길이는 현재 위치+1
        BigInt a = {action+i,pos+1}
        BigInt b = a*a*a
        if (b(pos) = n(pos))
            if (recur(b, pos+1, action+i))
                return 1;
    return 0;
}

소스 코드

#include <iostream>
#include <algorithm>
using namespace std;

#define all(v) v.begin(),v.end()
#define ist istream&
typedef string str;

struct big {
    str v;
    int n;
} n;

ist operator >> (ist in, big &b) {
    in >> b.v;
    reverse(all(b.v));
    b.n = b.v.size();
    return in;
}

big operator * (big a, big b) {
    int p,k,m;
    m = a.n+b.n+1;
    str c(m, 0);
    for (int i=0; i<a.n; i++) {
        int d = 0;
        for (int j=0; j<b.n; j++) {
            k = i+j;
            p = (a.v(i)-'0')*(b.v(j)-'0')+d+c(k);
            d = p / 10;
            c(k) = p % 10;
        }
        if (d) c(i+b.n) += d;
    }
    while (!c(m-1)&& m>1) m--;
    c = c.substr(0,20);
    for (auto &x:c) x+='0';
    return {c.substr(0,m), m};
}

bool rec(big v, int c, str r) {
    if (c==n.n) {
        while (r.back()=='0')
            r.pop_back();
        reverse(all(r));
        cout << r << "\n";
        return 1;
    }
    if (v.v(c)==n.v(c))
        return rec(v,c+1,r+'0');
    if (!v.v(c)&&n.v(c)=='0')
        return rec(v,c+1,r+'0');
    for (char i='0'; i<='9'; i++) {
        big a = {r+i,c+1};
        big b = a*a*a;
        if (b.v(c)==n.v(c))
            if (rec(b,c+1,r+i))
                return 1;
    }
    return 0;
}

void test() {
    cin >> n;
    rec({"",0},0,"");
}

int main() {
    int t;
    cin>>t;
    while(t--) test();
}