#10965 제곱수 만들기

[sincheol]

input : A 자연수 A에 자연수 B를 곱해 어떤 수 C의 제곱 수가 되게하는 B를 구하라

[sincheol]

처음에는 소수인지 아닌지 판별하는 함수를 만들어서 소수인지 확인을 한 후 나눴음

[sincheol]

답은 나오지만 제한시간 초과.. 그것도 몇 문제를 풀지못함.. 계속 코드를 보다 보니 어차피 1부터 시작해서 계속 나누고 나눠떨어지지 않으면 그 수를 증가시켜 나눈다는 생각 자체가 소인수분해 즉 소수로 계속 나눠진다는 것을 깨달음.. 그래서 소수인지 확인하는 코드를 삭제하니 1000문제밖에 못풀던 코드가 8만개 넘게 풀림.. 여기서 시간을 더 줄여야 하는데 검색없이는 못할듯..

[sincheol]

답은 나오지만 제한시간 초과.. 그것도 몇 문제를 풀지못함.. 계속 코드를 보다 보니 어차피 1부터 시작해서 계속 나누고 나눠떨어지지 않으면 그 수를 증가시켜 나눈다는 생각 자체가 소인수분해 즉 소수로 계속 나눠진다는 것을 깨달음.. 그래서 소수인지 확인하는 코드를 삭제하니 1000문제밖에 못풀던 코드가 8만개 넘게 풀림.. 여기서 시간을 더 줄여야 하는데 검색없이는 못할듯..

또한 반복문을 O(A의 루트를 씌운 값) 만큼만으로 줄임..

[sincheol]

A의 최대가 10000000.. 2의 제곱으로 표현하자면 약 24승 정도 즉 어떤 수를 소수로 표현하면 개수가 24보단 작다.. 이것을 이용해 배열의 크기도 줄이고 반복문도 줄였음.. 각 input에 대해 최대의 약수개수를 구해 반복문을 줄이면 시간이 좀 더 줄어질것 처럼 보임..

[sincheol]

A의 최대가 10000000.. 2의 제곱으로 표현하자면 약 24승 정도 즉 어떤 수를 소수로 표현하면 개수가 24보단 작다.. 이것을 이용해 배열의 크기도 줄이고 반복문도 줄였음.. 각 input에 대해 최대의 약수개수를 구해 반복문을 줄이면 시간이 좀 더 줄어질것 처럼 보임..

해보니 더 오래걸림...

[sincheol]

1000단위로 끊어서도 한번 배열과 for문을 줄여보려했는데 오히려 if문을 쓰면 쓸수록 시간이 오래 걸리는 듯..

[sincheol]

84000개 정도면 정말 내가 사용하는 메서드의 시간차이로 안되는 듯... 전에 scanner에서 buffered reader로 바꿔서 시간차이를 채감한것 처럼 이번에도 testcase가 10만개이니 system out으로 프린트하기 보다는 buffered writer를 사용해 시간이 얼마나 차이나는지 실험해봄

[sincheol]

성공... 확실히 test case가 많을 때는 buffer를 사용해 빠른 입출력을 사용하는 것이 실(메모리)보다는 득이 훨씬 많은 듯하다...

[sincheol]

실행시간이 제일 작은 코드를 보니 우선 루트A보다 작은 수들 중 소수를 찾아 그 소수들을 제곱한 후 루트A만큼 반복하면서 그 값으로 A를 나눠 나머지를 프린트..