WEIRD - Java 짋문이요..!

  • ehdwns2045
    ehdwns2045

    이번엔 WEIRD문제에서 오류가 있어,
    이렇게 질문드립니다.!

    조건에 대해 약수들의 합이 원래 수보다 큰 경우에 대해
    약수의 합으로 원래의 수가 되는 경우가 있는지 판단하였습니다.
    판단방법으로는 남은 약수들의 합과 원래의 수를 비교한 차를 구하고
    남은 약수들의 합이 위에서 구한 수가 되는지 비교하였습니다.
    약수들의 합에 대해서는 구했던 수보다는 작지만 약수들중에는
    가장 높은 숫자를 빼도록 하여, 위 과정을 반복하여
    차가 0이 될 경우 weird가 아님을 증명하게 됩니다.

    위 과정에서 차가 0기 되지 않고 루프를 돌 경우를 대비해,
    depth를 추가하여 10번의 루프루 false로 나오도록 하였구요.

    //70, 836, 4030, 5830, 7192, 7912, 9272, 10430, 10570, 10792,
    //10990, 11410, 11690, 12110, 12530, 12670, 13370, 13510, 13790,
    //13930, 14770, 15610, 15890, 16030, 16310, 16730, 16870, 17272,
    //17570, 17990, 18410, 18830, 18970, 19390, 19670

    인터넷상에서 얻은 weird 숫자들에 대한 테스트는 전부 잘 통과하였는데, 어느 부분에서 문제가 있을까요..?

    많은 조언 부탁드립니다.!

    import java.util.ArrayList;
import java.util.Scanner;

//70, 836, 4030, 5830, 7192, 7912, 9272, 10430, 10570, 10792,
//10990, 11410, 11690, 12110, 12530, 12670, 13370, 13510, 13790,
//13930, 14770, 15610, 15890, 16030, 16310, 16730, 16870, 17272,
//17570, 17990, 18410, 18830, 18970, 19390, 19670

public class WEIRD {

    static int depth = 0;

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner input = new Scanner(System.in);

        int count = Integer.parseInt(input.nextLine());
        int loop_count = 0; 

        if(count <= 200) {

            while(loop_count < count && input.hasNext()){

                int num = Integer.parseInt(input.nextLine());

                if(num > 1 && num < 500000) {
                    depth = 0;
                    checkWeird(num);    
                } else {
                    System.exit(0);
                }

                loop_count++;
            }

        } else {
            System.exit(0);
        }

    }

    public static void checkWeird(int num) {

        ArrayList<Integer> div_list = divisionNumbers(num);
        int sum = 0;

        boolean step1 = false;

        for(int i=0; i<div_list.size(); i++) {
            sum += div_list.get(i);
//          System.out.println("Original division Number"+"["+ i +"] : " + div_list.get(i));
        }

//      System.out.println("Sum : " + sum + "/ Num : " + num);

        if(sum <= num) {
            System.out.println("not weird");
        } else {
            int check_num = sum - num;

            for(int j=0; j<div_list.size(); j++) {

                if(div_list.get(j) == check_num ) {
                    System.out.println("not weird");
                    step1 = true;
                    break;
                } else if(div_list.get(j) > check_num) {
                    div_list.remove(j);
                }
            }

            if(!step1) {
                if( GreedyCheck(div_list, check_num ) ) {
                    System.out.println("not weird");
                } else {
                    System.out.println("weird");
                }
            }

//          if(!step1 && !step2) {
//              System.out.println("weird");
//          }

        }


    }

    public static ArrayList<Integer> divisionNumbers(int num) {

        ArrayList<Integer> div_list = new ArrayList<Integer>();
        ArrayList<Integer> div_buffer = new ArrayList<Integer>();

        int index_count = 1;

        div_list.add(1);

        for(int i=2; i<730; i++) {

            if(num%i == 0) {
                int div_num = num/i;

                if(i < div_num){

                    div_list.add(i);
                    div_buffer.add(div_num);

                    index_count += 2;
                } else if (i == div_num) {
                    div_list.add(i);
                    break;
                } else {
                    break;
                }

            }

        }

        for(int i=0; i<div_buffer.size(); i++) {
            div_list.add(div_buffer.get( (div_buffer.size()-1)-i) );
        }

        return div_list;

    }

    public static boolean GreedyCheck(ArrayList<Integer> div_list, int goal_num) {

        depth++;

        for(int i=div_list.size()-1; i>=0; i--) {

//          System.out.println("Edit division Number"+"["+ i +"] : " + div_list.get(i));

            if(div_list.get(i) <= goal_num ) {
                goal_num -= div_list.get(i);
                div_list.remove(i);
                break;
            }

//          System.out.println("Edit division Number"+"["+ i +"] : " + div_list.get(i));
        }

//      System.out.println( "goal : " + goal_num );

        if(goal_num == 0) {
            return true;
        } else if(depth == 10) {
            return false;
        } else {
            return GreedyCheck(div_list, goal_num);
//          return false;
        }


    }

}

    9년 전
0개의 댓글이 있습니다.

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