http://ergate.tistory.com/entry/Codility-ChocolatesByNumbers


이전 문제의 정확한 해법이다.

문제 카테고리가 유클리드 알고리즘이어서 뭔가 하고 알아봤다.


https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95#%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98


두 수가 주어졌을 때, 거기에서 최대 공약수를 구하는 알고리즘이다.

그리고 이 문제의 정답은 (N / 최대공약수)와 동일하다.



int solution(int N, int M)
{
    int nRet = 0;
    
    if( N > 0 && M > 0 )
    {
        int nTarget = N;
        
        while( N % M != 0 )
        {
            N %= M;
            swap(N, M);
        }
        
        nRet = nTarget / M;
    }
    
    return nRet;
}



전체적으로 훨씬 간결해졌다.

원래 0이 나오면 해야하는 처리도 해야하지만, 문제에서 N과 M은 1부터 시작한다고 정의하고 있다.

기존 LeetCode에서는 볼 수 없던 문제 유형이어서 새로운 것을 알게 되었다는 느낌이 든다.

정확도 100%, 성능 100%

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

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

[Codility] ChocolatesByNumbers  (0) 2017.12.06
[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

+ Recent posts