주어진 N이 사각형의 넓이라고 한다면, 이를 기준으로 가장 작은 사각형의 둘레를 구해서 return하면 된다.

왜 time complexity가 O(sqrt(N))일까 고민을 조금 했는데, 시작부터 sqrt를 하고, 여기에서 빼면서 나아가면 구할 수 있다는 것을 알았다.

어떻게 접근할지 방법만 알면 나머지는 간단하다.



#include <math.h>

int solution(int N)
{
    int nRet = 0x7FFFFFFF;

    int nWidth = sqrt(N);
    int nHeight;
    
    while( nWidth > 0 )
    {
        if( N % nWidth == 0 )
        {
            nHeight = N / nWidth;
            nRet = min( nRet, (nWidth + nHeight) * 2 );
        }
        
        --nWidth;
    }
    
    return nRet;
}



그나저나 오랜만에 스킨 한번 변경했는데(트렌드라고 할 수 있는 반응형으로...) 기존 소스가 보이지 않는 부분이 있을 듯 하다.

저작자 표시 비영리 변경 금지
신고

'Programming > C,C++' 카테고리의 다른 글

[Codility] ChocolatesByNumbers  (0) 2017.12.06
[Codility] CountFactors  (0) 2017.12.06
[Codility] MinPerimeterRectangle  (0) 2017.12.06
[Codility] MaxProfit  (0) 2017.12.06
[Codility] Dominator  (0) 2017.12.05
[Codility] StoneWall  (0) 2017.12.05

+ Recent posts