Weird number 문제 관련 질문이 있습니다 uyen 일단 코드는 다음과 같습니다 #include<iostream> #include<vector> using namespace std; int divisor[1000]; bool checkEqual(int num, int index); //약수 조합의 합이 같은지 아닌지 판단 int main() { int T, num, sumDiv; int index; bool isequal; cin >> T; while(T-- > 0){ cin >> num; isequal = true; if(num%2 == 0){ index = 0; sumDiv = 0; for(int i = 1; i*2 <= num; i++){ if(num%i == 0){ divisor[index++] = i; sumDiv += i; } } if(sumDiv > num) isequal = checkEqual(num, index-1); } if(isequal) cout << "not weird" << endl; else cout << "weird" << endl; } } bool checkEqual(int num, int index) { int i; for(i = index; i >= 0; i--){ if(divisor[i] <= num) break; } if(i < 0) return false; if(num-divisor[i] == 0) return true; for(int j = i; j >= 0; j--){ for(int k = j-1; k >= 0; k--){ if(checkEqual(num-divisor[j], k)) return true; } } return false; } bool checkEqual(int num, int index) { int i; for(i = index; i >= 0; i--){ if(divisor[i] <= num) break; } if(i < 0) return false; if(num-divisor[i] == 0) return true; if(checkEqual(num-divisor[i], i-1)) return true; else return checkEqual(num, i-1); } 그리고 제가 checkEqual 함수를 두개 만들어봤는데 위에꺼는 시간 초과이고 아래는 110ms정도만에 통과하던데요 똑같은 알고리즘으로 구현한것 같은데 시간이 20배가 넘게 차이가 나네요... 저도 모르게 다른 알고리즘을 쓴건지.. 아니면 다른 이유가 있는건지 알려주시면 감사하겠습니다 11년 전
3개의 댓글이 있습니다. Kureyo ~code c++로 묶어주세요 ㅠㅠ 11년 전 link uyen 깜빡했네요 죄송합니다 ㅋㅋ 11년 전 link JongMan 본인도 모르게 다른 알고리즘을 쓰신 것이 맞습니다. 전자에서는 같은 인자를 갖는 checkEqual()이 여~~~~러번 호출되게 됩니다. 한번 checkEqual()이 한번 호출될 때마다 printf()를 해보시면 확 느낌이 오실겁니다. 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
uyen
일단 코드는 다음과 같습니다
그리고 제가 checkEqual 함수를 두개 만들어봤는데 위에꺼는 시간 초과이고 아래는 110ms정도만에 통과하던데요
똑같은 알고리즘으로 구현한것 같은데 시간이 20배가 넘게 차이가 나네요...
저도 모르게 다른 알고리즘을 쓴건지.. 아니면 다른 이유가 있는건지 알려주시면 감사하겠습니다
11년 전