[알고리즘] Greedy algorithm - 이집트 나눗셈(cpp)

문제
이집트 나눗셈을 하는 프로그램을 작성하시오.
입력
p/q를 나타내는 두 정수 p, q가 사이에 공백을 하나 두고 주어진다.
p는 1 이상 1,000 이하, q는 p+1 이상 2,000 이하인 정수
출력
수업 시간에 배운 이집트 나눗셈의 결과로 몇 개의 분수가 나오는지 출력한다. 예를 들어, 5/6은 1/2 + 1/3이므로 2개의 분수가 필요하다.

예제 입력 1
5 6
예제 출력 1
2
예제 입력 2
19 20
예제 출력 2
4

---

알고리즘 수업의 첫 과제였다.

 

이집트 나눗셈이란, 유리수 p/q가 주어지면 분자가 1인 분수들의 합으로 p/q를 표현하는 것이다.

예) 5/6 = 1/2 + 1/3 , 3/4 = 1/2 + 1/4

 

욕심쟁이 기법, 흔히 Greedy 알고리즘이라고 부르는 기법을 사용하여 풀이할 수 있다.

 

수업 시간에는 두 가지의 해결법을 배웠다.

첫번째 방법이다.

n= 2, 3, ... 해보면서, 1/n과 p/q 중 어느 수가 더 큰지 생각해보자.
1/n이 더 크다면 n:= n+1, 아니면 p/q = p/q - 1/n 으로 계속 문제를 풀자. p/q가 0이 되면 종료한다.

p/q = 5/6이면 1/2 < 5/6
5/6 - 1/2 = 2/6 = 1/3
p/q = 1/3이면 1/2 > 1/3. 1/3 <= 1/3.
p/q = 1/3 - 1/3 = 0 으로 종료.

 

단순히 하나씩 비교해서 연산하는 방법이다.

하지만 위 방법은 분모의 값이 커질수록 비효율적이다. 분모가 아주 큰 숫자라면, 시간도 아주 오래 걸릴 것이다.

 

 

그렇다면, 두 번째 방법을 살펴보자

주어진 수 p/q에 대해서, 이 수의 역수 q/p와 같거나 큰 가장 작은 정수 [q/p]를 찾고, 1/[q/p]를 p/q에서 뺀다.
이 과정을 0이 될때까지 반복한다.

5/6 에 대해서, [6/5] = 2.
5/6 - 1/2 = 1/3
1/3 에 대해서, [3/1] = 3. 1/3 - 1/3 = 0.

 

역수를 활용한다면 훨씬 빠르고 효율적으로 이집트 나눗셈을 할 수 있다.

분모를 1씩 증가시켜 연산하는 대신, 역수를 사용하여 1/[q/p]에 바로 접근할 수 있다는 차이가 있다.

 

이 두번째 방법을 사용하여 과제를 해결하였다.

#include <iostream>
#include <numeric>
using namespace std;

int main(){

    int p, q;
    int n = 1;
    int cnt = 0;
    cin >> p >> q; // p/q
    // if(p<1 || p>1000 || q<p || q>2000)

    while(p > 0){
        cnt++;
        while(1){ 
            if(n > q/p) break;
            n++;
        }
        p = p*n - q;
        q = q * n;
        int tmp = gcd(p, q);
        p /= tmp;
        q /= tmp;
        if(p == 1) { cnt++; break; }
    }
    cout << cnt;
    return 0;
}

 

결과는 만점!