Codility Java ChocolatesByNumbers

문제

Link

코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
  public int solution(int N, int M) {
    return N / getGcd(M, N);
  }
  // Euclidean algorithm.
  private int getGcd(int num1, int num2) {
    if (num1 % num2 == 0) {
      return num2;
    } else {
      return getGcd(num2, num1 % num2);
    }
  }
}

설명

1. 유클리드 호제법¹을 사용하여 1에서 부터 주어진 정수 N까지 M을 이용해서 최대 공약수를 먼저 구한다.
2. 주어진 정수 N을 유클리드 호제법을 통해 구한 최대 공약수로 나누어서 나온 먹을 초콜릿의 개수를 주어진 문제의 결과로 반환한다.

결과

Link

소스

Sample Code는 여기에서 확인 가능합니다.

Reference

1. Wiki-Euclidean_Algorithm ↩