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

  • jangwhdgns
    jangwhdgns

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

    아래 소스는 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;
        }
    }
    

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

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

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


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