poly 문제에 대해서 질문입니다.

  • BadCandy
    BadCandy

    import java.util.Arrays;
    import java.util.Scanner;

    public class POLY {

    private static int[][] cache = new int[101][101];
    
    private static int n;
    
    private static final int MOD = 10000000;
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
    
        Scanner sc = new Scanner(System.in);
    
        int C = sc.nextInt();
    
        for (int i = 0; i < C; i++) {
    
            n = sc.nextInt();
    
            for (int j = 0; j < 101; j++) {
                Arrays.fill(cache[j], -1);
            }
    
            System.out.println(maxPoly());
    
        }
    }
    
    private static int poly(int n, int first) {
    
        if (n == first)     return 1;
    
        if (cache[n][first] != -1)  return cache[n][first];
    
        int ret = cache[n][first] = 0;
    
        for (int second = 1; second <= n-first; second++) {
            int add = second + first - 1;
            add *= poly(n - first, second);
            add %= MOD;
            cache[n][first] = (ret += add);
            cache[n][first] = (ret %= MOD);
        }
    
        return ret;
    }
    
    private static int maxPoly() {
        int ret = 0;
        for (int j = 1; j <= n; j++) {
            ret += (poly(n, j) % MOD);
        }
    
        return ret;
    }

    }

    코드는 정상적으로 짠거같은데 예제 3번째 입력

    92에 대해서 예제 출력인 4841817이 나오지 않고

    394841817가 출력이 됩니다.

    맞게 코드를 짰다고 생각하는데.. 제가 놓친 부분이 있을런지요..?


    2년 전
2개의 댓글이 있습니다.
  • Being
    Being

    보통 느리지만 작은 입력을 완전히 맞는 코드를 따로 구현하여 비교하라고 말씀을 드리겠지만, 이번 경우에는 예제 출력과 실제 답 사이의 차이를 눈여겨 보시기 바랍니다.


    2년 전 link
  • BadCandy
    BadCandy

    아아..... 초보적인 실수를 저질렀었군요
    감사합니다 ㅎㅎ


    2년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.