[2023-01-17]

Start

어제 풀다가 내팽겨친 [2023-01-16]..그대로..

 

 

MinPerimeterRectangle 문제

A * B = N으로 약수를 구해서 푸는 문제라고 생각했다.

문제는 내가 아는 약수를 구하는 알고리즘은 시간복잡도가 너무 컸다.

 

1부터 하나씩 대입해보는 방식으로 O(N)이라 입력값이 너무 클 경우 제한된 시간을 초과하게 된다.

 

그래서 찾아보았는데, [알고리즘] 효율적으로 약수를 찾는 알고리즘 이라는 글을 찾아보게 되었다.

 

블로그에서 알게된 방법인데

 

1부터 N의 제곱근까지만 0으로 나누어 떨어지는지 확인하면 된다고 한다..!

 

나누어떨어진 수를 N에 나누면 추가로 약수를 구할 수 있다.

 

그래서 위의 방식을 이용해서 문제를 풀 수 있었다.

1부터 N의 제곱근까지의 수까지만 N에 나눠서 0이 나오면 약수이다.

이렇게 구한 수를 다시 N에 나눠서 나오는 값도 약수이다.

 

각각 나온 수를 더하고 곱해서 최소값인지 비교하면 된다.

 

CountFactors 문제

 

위의 문제와 동일하게 약수 관련 문제였고 약수의 개수를 구하는 문제였다.