17103번 - 골드바흐 파티션
에라스토테네스의 체로 소수 구했다고 다가 아니네요...
가장 먼저 떠오르는 방법이
1. 인풋값을 저장한다.
2. 체를 활용해 소수를 구한다.
3. 이중루프 돌면서 두 소수의 합과 (다시 루프 또 돌면서)인풋값을 비교한다.
일 텐데,
이대로 해선 시간초과 나오네요. 3번의 O(N^2 * M) 시간복잡도를 어떻게든 낮추는 것이 이 문제의 핵심 키포인트입니다.
질문게시판에서 얻은 핵심 힌트는 (인풋값 - 소수) 의 결과값이 소수인가(bool)?를 확인하는 것이었습니다.
어디선가 bool값 모아놓은거 구해놨었잖아요?
단순하게 생각했다가 10회제출하고 고통받았네요 ㅠㅠ
저처럼 고통받으시는분들 약간의 실마리라도 얻으시라고 올려봅니다.
댓글을 작성하려면 로그인해야 합니다.
ekdrn1 2년 전 5
에라스토테네스의 체로 소수 구했다고 다가 아니네요...
가장 먼저 떠오르는 방법이
1. 인풋값을 저장한다.
2. 체를 활용해 소수를 구한다.
3. 이중루프 돌면서 두 소수의 합과 (다시 루프 또 돌면서)인풋값을 비교한다.
일 텐데,
이대로 해선 시간초과 나오네요. 3번의 O(N^2 * M) 시간복잡도를 어떻게든 낮추는 것이 이 문제의 핵심 키포인트입니다.
질문게시판에서 얻은 핵심 힌트는 (인풋값 - 소수) 의 결과값이 소수인가(bool)?를 확인하는 것이었습니다.
어디선가 bool값 모아놓은거 구해놨었잖아요?
단순하게 생각했다가 10회제출하고 고통받았네요 ㅠㅠ
저처럼 고통받으시는분들 약간의 실마리라도 얻으시라고 올려봅니다.