[171208][Codility](C#)ChocolatesByNumbers

링크 : https://codility.com/programmers/lessons/12-euclidean_algorithm/chocolates_by_numbers/

 

문제>

N개 들어있는 초콜렛 상자에서 M개씩 먹는다.

만약 M개씩 먹다가 초콜렛상자에 M보다 적게 남으면 다음 상자 추가 개봉.

추가 상자를 열지 않아도 될 때 멈추고 몇개의 초콜렛을 먹었는지 출력하라.

 

해결방법0.(정확도 100%, 퍼포먼스 75%)

 

using System;

class Solution {
    public int solution(int N, int M) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int n = N;
        int count = 0;
       
        while(true)
        {
            if(n < M)
            {
                n += N;    
                continue;           
            }
            n -= M;
            count += 1;   
           
            if(n == 0) break;       
        }
        return count;
    }
}

 

해결방법1.(정확도 100%, 퍼포먼스 100%)

최대 공약수를 구해서 해결.

재귀로 나머지가 0이 나올때 까지 나머지로 계속 나머지를 구한다.

마지막 값으로 초콜렛을 나누면 최대 먹을 수 있는 초콜렛 수. 

using System;

class Solution {
    public int solution(int N, int M) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        return N / gcd(N, M);
    }
    public int gcd(int n, int m)
    {
        if(n % m == 0)
        {
            return m;
        }
        else
        {
            return gcd(m, n % m);
        }
    }    
}

 

17.12.08(0200)

회고 : 퍼포먼스 잡겠다고 최소공배수 구하고 퍼포먼스 더 늘어나고 ㅠㅠ 삽질했는데 하다하다 안되겠어서 참고.

최대공약수를 구하면 되는 문제였다 ㅠ