wield problem 관련해서 도움 요청드립니다....

  • User Avatar
    jangwhdgns

    안녕하세요.
    [[연습 문제 wield problem |problem:WEIRD]] 관련해서 도움 요청드립니다.

    아래 소스는 java로 구현하였구요, 테스트 데이터를 넣었을 때 맞는 답이 나오는거 같은데
    자꾸 오답이라고 뜨네요.. 8번째 시도 후 이렇게 질문을 드려요. 어떤 부분이 잘못 되어있는지
    알려주시면 정말 감사하겠습니다.

    제가 이러한 알고리즘 문제를 처음 접해보아서 너무 신기하고 재미있네요.
    초반에 조금 도움을 주시면 저도 질문답변 란에 기여할 수 있도록 하겠습니다.

    testCase
    [input]
    4
    6
    [output]
    not weird
    [input]
    12
    [output]
    not weird
    [input]
    70
    [output]
    weird
    [input]
    481200
    [output]
    not weird

    이와 같이 나옵니다. 제가 틀린건가요? ㅠㅠ

    • 소스코드
    
    import java.util.*; 
    
    public class Main {
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            
            int cases = sc.nextInt();
            if(cases > 200){
                return;
            }
            while(cases-- > 0) {
                Boolean isWeird = false;
                int chkNumber = 0;
                ArrayList<Integer> list;
                
                String num = sc.next();
                chkNumber = Integer.parseInt(num);
                
                if(chkNumber >= 500000 || chkNumber <1){
                    return;
                }
                
                list = getDivisor(chkNumber);
    
                int listTotalSum = 0;
                for (int i = 0; i < list.size(); i++) {
                    listTotalSum += list.get(i);
                }
                
                if(listTotalSum <= chkNumber){
                    isWeird =false;
                }else{
                    int count = list.size();
                    int pow = (int)Math.pow(2, (double)count);
                    
                    for (int i = 0; i < pow; i++) {
                        int subsetSum = 0;
                        
                        for (int j = 0; j < count; j++) {
                            {
                                if((i&(1<<j)) > 0){
                                    subsetSum += list.get(j);
                                    if(subsetSum >= chkNumber){
                                        break;
                                    }
                                }
                            }
                        }
                        if(subsetSum == chkNumber){
                            isWeird = false;
                            break;
                        }else{
                            isWeird = true;
                        }
                    }
                }
                if(isWeird){
                    System.out.println("weird");    
                }else{
                    System.out.println("not weird");
                }
            }
            
        }
        // 약수 반환 메서드
        private static ArrayList<Integer> getDivisor(int num) {
            ArrayList<Integer> divisorList = new ArrayList<Integer>();
           
            for(int i = num-1; i>0; i--) {
                if(num%i==0)
                {
                    divisorList.add(i);        //나누어떨어지면 약수 등록(내림차순등록)
                }
            }
            return divisorList;
        }
    }
    
    

    12년 전
1개의 댓글이 있습니다.
  • User Avatar
    Being

    가장 약수가 많은 수의 경우 그 수가 100가지를 가뿐히 넘깁니다. 따라서 $2x$개의 모든 경우의 수를 조사하는 방법으로는 해결하기 어려우실 것입니다. 이하는 힌트입니다.


    테스트 데이터가 약해 몇몇 편법으로 통과한 풀이가 있지만, 원칙적으로 풀기 위해서는 동적 계획법, Dynamic Programming 이라는 개념이 필요합니다.
    해당 개념으로 해결할 수 있는 문제들 중 가장 쉬운 축에 속하므로 한번 해결해보시기를 권합니다.


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