[국비지원] 17일차- 프로그래머스.피자 나눠 먹기(2) GCD, LCM

 

오늘의 문제

 

class Solution {
    public int solution(int n) {
        int result = 0;
        loop:
        for(int i = 1; i<100; i++){
            for(int j = 1; j<=6; j++){
            // 피자수 = i , 인당 조각수 = j
                if((i*6) == (n*j)){
                    result = i;
                    break loop;
                }   
            }
        }
        return result;
    }
}

 

result(피자수) * 6 와 n * 인당 피자 조각수가 같으면 되는 문제였기에 이렇게 풀었다.

나중에 다른 분들 풀이를 확인하니 조각수까지는 구할 필요가 없었다...!

 

다른 풀이 중에서 최소공배수와 최대공약수를 사용해서 문제를 푸신 분도 있었는데 이해하느라 한참 걸려서 정리해본다

 

class solution{
	public int GCD(int num1, int num2){
    	if(num1 % num2 == 0)
        	return num2;
        else
        	return GCD(num2, num1 % num2);
    }
    
    public int LCM(int num1, int num2){
    	num1 * num2 / GCD(num1, num2);
    }
    
    public int solution(int n){
    	return LCM(n, 6) / 6;
    }
}

 

위에서 말했듯 (n :사람수) * (피자조각수) = (피자수) * 6의 식이 만들어지기 때문에

n과 6의 값이 주어졌을 때 좌항과 우항은 이 둘의 최소공배수를 구한 후, n과 6의 최소공배수를 제외한 서로소를 구하고

좌항과 우항에 서로소를 각각 반대로 곱하면 같아진다.

 

예를 들어 인원수(n)이 15라고 했을 때

 

15 * 조각수 = 6 * 피자수

 

이는

 

3 * 5 * 조각수 = 2 * 3 * 피자수

 

와 같고 이 둘의 최소공배수는 2 * 3 * 5이기 때문에 각각의 서로소인 2와 5를 조각수와 피자수에 대입해주면 된다.

 

서로소와 최소공배수는 최소공약수를 알아야 하기 때문에 n과 6의 최대공약수를 구해야 한다.

최대공약수는 유클리드 호제법이라는 알고리즘을 통해 구할 수 있다

유클리드 호제법

A와 B의 두 수가 있을 때, 두 수의 나머지의 값이 0이 될 때까지

B를 A와 B의 나머지로 나누면 마지막으로 나눈 값이 두 수의 최대공약수가 되는 법칙이다

 

https://kdhsmarto.tistory.com/m/15

'최소 공배수' 와 '최대 공약수', '유클리드 호제법' 과 '서로소'.

 

A = aG, B = bG 라 할 때,

 

GCD // 최대공약수 구하기

return G (최대공약수)

 

LCM // 최소공배수 구하기

return aG * bG / G

// a* b * G (최소공배수)

 

solution // 서로소 구하기

return a * b * G / bG

// a

// a는 피자수

 

 

TIL

---

https://abc-datatype.tistory.com/58

[JAVA] 2차원 배열, 다차원 배열

 

 

 

 

 

 

오늘의 플레이리스트...