피자를 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)를 구하기 위해 재귀함수를 이용한다.
'Java > Coding Test' 카테고리의 다른 글
| 팩토리얼 (0) | 2023.09.11 |
|---|---|
| 숫자 찾기 문제풀이 (0) | 2023.09.10 |
| 외계행성의 나이 문제풀이 (0) | 2023.09.10 |
| 문자열 정렬하기(1) 문제풀이 (0) | 2023.09.10 |
| 점의 위치 구하기 문제풀이 (1) | 2023.09.09 |