강의로 돌아가기
홍성현

[코드 포함] 반례를 못 찾겠어요.

안녕하세요. 이 문제를 계속 푸는데 로직의 어디가 문제인지, 반례가 무엇인지 찾지도 못해서 오랜 시간 고민하다가 결국 질문 올립니다.

include

include

using namespace std;
int block(long long n);

//begin이 1일 때는 0을 따로 넣어준다.
vector solution(long long begin, long long end) {
vector answer;

if(begin == 1) {
    answer.push_back(0);
    begin++;
}

for(long long i = begin ; i <= end; i++)
    answer.push_back(block(i));

return answer;

}

//if 소수면 1반환.
//else max(약수 <= 10000000)
// return 범위는 1 ~ 10000000
int block(long long n) {
long long max = 0;
//O(sqrt(n))
for(long long i = 2; i * i <= n; i++) {
if(n % i == 0) {
if(n / i <= 10000000)
return n / i;

        max = i;
    }
}

if(max > 0)
    return max;
else
    return 1;     //n이 소수 일 때

}

위는 제 코드인데, 도대체 어떤 반례가 존재하는걸까요? 효율성 테스트에서 전부 오답이 나오는데(시간초과X) 어떤 케이스를 놓치고 있는지 정말정말 궁금합니다!!

1 개의 답변
-

저도 효율성에서 오답 나왔었는데 if(n / i <= 10000000) 이부분 빼니까 통과하네요...

  • -
    999999999 , 1000000000 로 테스트 하면 [ 9009009, 10000000 ] 이게 나와야 되는건데 [333333333, 500000000] 이걸 요구하고 있는거죠.
    -―2018.07.19 11:55
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.