WEIRD 문제 오답 원인을 모르겠습니다.

  • whph1991
    whph1991

    WEIRD

    import java.util.Scanner;

    public class Main {
    public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    
        int cases = sc.nextInt();
    
        while (cases-- > 0) {
    
            int bucket [] = new int [200];
            int sum = 0, index = 0, j = 0;
    
            int N = sc.nextInt();
    
            //divisor를 구하여 bucket 배열에 오름차순으로 저장한다.
            for(int i = 1 ; i < N ; i ++){
                if(N%i == 0)
                    bucket[index++] = i;
            }
    
            //가장 큰 divisor의 index
            --index;
    
            //divisor의 합
            while(bucket[j] != 0){
                sum += bucket[j++];
            }
    
            if(sum > N && !condition2(N, 0, index, bucket))
                System.out.println("werid");
    
            else
                System.out.println("not werid");
        }
    }
    
    public static boolean condition2 (int N, int sum, int index, int bucket []){
        if(N < sum)
            return false;
    
        else if (N == sum)
            return true;
    
        while(index >= 0){
            sum += bucket[index--];
            if(condition2(N, sum, index, bucket))
                return true;
            else
                sum -= bucket[index+1];
        }
        return false;
    }

    }

    backtracking 기법으로 문제에 접근했는데
    오답이 발생합니다.

    50만까지 약수의 갯수를 확인한 결과
    한 숫자의 약수는 최대 199로 확인해서
    배열의 크기를 200으로 잡았습니다.
    어디서 문제가 생겼을까요...??

    ㅜㅜ


    7년 전
3개의 댓글이 있습니다.
  • Corea
    Corea

    오타가 있습니다. not weird예요!


    7년 전 link
  • whph1991
    whph1991

    감사합니다!!!ㅋㅋㅋㅋㅋㅋㅋ
    세상에 이걸로 몇시간이나 버리다니


    7년 전 link
  • wookayin
    wookayin

    ㅠㅠ
    제가 실제대회때 저거로 엄청 틀렸었죠(..)


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