피자 나눠먹기(2) 문제풀이 (with.유클리드 호제법)

피자를 6조각으로 나눌때 모든 사람이 피자를 남기지 않고 같은 수의 피자 조각을 먹는다면 최소 몇 판을 시켜야 하는지 반환

 

문제는 최소 공배수를 구할 수 있는지를 묻고 있다. 

 

->6의 배수 중에서 사람 수로 나누어 떨어지는 수를 구한다. 

-> 본인은 재귀함수를 이용해서 문제를 풀었다. 

n의 배수 중 6으로 나눠 떨어지는 수를 구하고 그때 6으로 나눈 값을 반환한다. 

n+=n; 코드를 실행하면서 n이 계속 바뀌어 n의 배수를 모두 계산할 수 없어 m을 따로 초기화 시켜 함수에 파라메터로 넣어주었다.

public int solution(int n) {

int m = n;

return recursiveCall(n,m);

}

public int recursiveCall(int n, int m){

if(n%6==0)return n/6;

else {

n+=m;

return recursiveCall(n,m);

}

}

이런 방식을 재귀함수를 이용하지 않고 풀면 

public int solution2(int n) {

int answer = 1;

 

while (true) {

if (6 * answer % n == 0)

break;

answer++;

}

 

return answer;

}

6에 피자 판수를 곱하고 사람수로 나누어 떨어질때까지 while문으로 체크하여 answer를 구한다.

 

->정석으로 최소 공배수를 구하여 6으로 나눈다. 

public int GCD(int num1, int num2) {

if (num1 % num2 == 0)

return num2;

return GCD(num2, num1 % num2);

}

 

public int LCM(int num1, int num2) {

return num1 * num2 / GCD(num1, num2);

}

 

public int solution3(int n) {

return LCM(n, 6) / 6;

}

 

GCD = 최대공약수 , LCM=  최소공배수 

 

LCM = num1 * num2 /GCD

> 두 수의 최소공배수는 두 수의 곱을 두 수의 최대공약수로 나누면 된다. 

 

유클리드 호제법에 따라 

자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라 한다면,

 >  a%b = r;

a,b의 최대공약수와 b,r의 최대공약수는 같다.

 > GCD(a,b) == GCD(b,r);

 

다시 b%r = r2;

GCD(b,r) == GCD(r,r2);

 

나머지가 0이 될 때의 나눈 수가 a,b의 최대공약수가 된다. 

만약 r%r2 == 0;

GCD(a,b) == GCD(b,r) == GCD(r,r2) == r2;

 

GCD(a,b)를 구하기 위해 재귀함수를 이용한다.