wield problem 관련해서 도움 요청드립니다.... 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개의 댓글이 있습니다. Being 가장 약수가 많은 수의 경우 그 수가 100가지를 가뿐히 넘깁니다. 따라서 $2x$개의 모든 경우의 수를 조사하는 방법으로는 해결하기 어려우실 것입니다. 이하는 힌트입니다. 테스트 데이터가 약해 몇몇 편법으로 통과한 풀이가 있지만, 원칙적으로 풀기 위해서는 동적 계획법, Dynamic Programming 이라는 개념이 필요합니다. 해당 개념으로 해결할 수 있는 문제들 중 가장 쉬운 축에 속하므로 한번 해결해보시기를 권합니다. 12년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
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
이와 같이 나옵니다. 제가 틀린건가요? ㅠㅠ
12년 전