[JAVA] 백준 1379 와 세제곱 (백트래킹 , 정수론)

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

2731번: 1379와 세제곱

문제 테스트 케이스 및 정답

http://acmgnyr.org/year2005/problems.shtml

2005 ACM Greater New York Regional Collegiate Programming Contest

 

세제곱 해서 1으로 끝나는 숫자는 어떻게 찾을 수 있을까요?

 

0부터 9까지 다 곱해보는 겁니다.

0*0*0 = 0
1*1*1 = 1
2*2*2 = 8
3*3*3 = 27
4*4*4 = 64
...
9*9*9 = 729

답은 1 입니다. 

 

그러면 세제곱해서 31로 끝나는 숫자는 어떻게 찾을 수 있을까요?

여기서 중요한 사실이 하나 있습니다.

1 * 1 * 1 = 1
11 * 11 * 11 = 1331
21 * 21 * 21 = 9261
31 * 31 * 31 = 29791
41 * 41 * 41 = 68921
51 * 51 * 51 = 132651
61 * 61 * 61 = 226981
71 * 71 * 71 = 357911
81 * 81 * 81 = 531441
91 * 91 * 91 = 753571

0부터 99까지 곱해보는 것이 아니라 1,11,21,31,41,51,61,71,81,91 중에 답이 있다는 것입니다.

왜냐하면 이미 끝자리가 1로 끝나는 세제곱수는 마지막 자리가 1인 것을 처음에 발견했기 때문입니다.

 

이부분이 핵심입니다. DFS를 이용하여 현재 길이 만큼 비교해가면서 끝자리가 일치하는지 확인해보면 됩니다.

 

여기서 또 문제가 하나 발생하는데 만약 답이  X = 9876543213 이라면 어떨까요?

long으로 선언해도 제곱조차 안됩니다. 그래서 곱셈을 따로 재정의 하여 구현해야합니다.

 

하지만 고맙게도 자바에는 BigDecimal 이라는 패키지를 통해서 큰 수의 곱셈을 지원합니다.

10^30 도 무난하게 곱셈을 하니 이 패키지를 이용하여 DFS를 단순하게 만들 겁니다.

 

아래 곱셈로직을 잠깐 보겠습니다.

String nextNum = String.valueOf((char) (i + '0')) + sb; // 다음 수 정하기 i = 0 ~ 9
BigDecimal bigNum  = new BigDecimal(nextNum); // bigDecimal로 변환
BigDecimal mulResult = bigNum.multiply(bigNum).multiply(bigNum); // 세제곱 실행!
StringBuilder mod = new StringBuilder(mulResult.toString()); // 결과를 String으로 변환

while(mod.toString().length() < ret.length()) {  // ret 와 mod 의 길이를 맞춤
  mod.insert(0, "0");
}

String cmp = mod.substring(mod.length() - (len + 1));

if(cmp.equals(ret)) {
    dfs(new StringBuilder(nextNum));
}

nextNum 은 현재 진행중인 문자열 (sb) 에 대해서 맨 앞자리에 0부터 9까지 문자열 덧셈을 하는 로직입니다.

예를 들어, sb = "1" 이라면 nextNum = "01" , "11", "21", "31", ... "91" 입니다.

nextNum을 세제곱하여 나온 결과가 mulResult 입니다. 

여기서 중요하게 처리해야할 예외가 하나 있습니다.

바로 "01" 인경우 입니다. "01"을 세제곱하면 "1" 입니다. 하지만 2자리수를 맞춰서 문자열을 비교해야합니다.

그래서 mod 의 길이와 ret의 길이를 맞추는 작업을 해줘야 합니다.

 

참고로 ret 는 저희가 찾아야할 끝자리 숫자를 자리수 별로 자른 문자열입니다.

ret 예를 들면 , 만약 s = 9876543213 이라면 ret = 3, 13 , 213 , 3213 , 43213, 543213 , ... 9876543213 입니다.

 

마지막으로 정답을 구했다면 Long 으로 파싱 해 줘야 합니다.

왜냐면 "000013" 으로 정답이 나왔다면 답은 13으로 반환해야 하기 때문입니다.

package boj.P2731;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.util.StringTokenizer;

public class Main {
    static Fs fs = new Fs();
    static String ans = "";
    static String s = "";
    static String[] piece;
    public static void main(String[] args)  throws Exception{
        int t = fs.nInt();
        while(t-- > 0) {
            s = fs.next();
            piece = new String[s.length()];
            for(int i=1;i<=s.length();i++) {
                piece[i-1] = s.substring(s.length()-i);
            }
            dfs(new StringBuilder());
            System.out.println(Long.parseLong(ans));
        }

    }

    static void dfs(StringBuilder sb) {
        int len = sb.length();
        if(len == s.length()) {
            ans = sb.toString();
            return;
        }

        String ret = piece[len];

        for(int i=0;i<10;i++) {
            String nextNum = String.valueOf((char) (i + '0')) + sb;
            BigDecimal bigNum  = new BigDecimal(nextNum);
            BigDecimal mulResult = bigNum.multiply(bigNum).multiply(bigNum);
            StringBuilder mod = new StringBuilder(mulResult.toString());
            while(mod.toString().length() < ret.length()) mod.insert(0, "0");
            String cmp = mod.substring(mod.length() - (len + 1));
            if(cmp.equals(ret)) {
                dfs(new StringBuilder(nextNum));
            }
        }
    }

    static class Fs{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public int nInt() throws Exception{
            return Integer.parseInt(next());
        }

        public String next() throws Exception{
            while(!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
    }
}