알고리즘/백준(BOJ)
[백준/C++] 4587번 이집트 분수
https://www.acmicpc.net/problem/4587 4587번: 이집트 분수 입력으로 주어진 분수 M/N이 다음과 같이 나타낼 수 있다면, D1, D2, D3, ...를 공백으로 구분해 출력한다. (D1 ≤ D2 ≤ D3 ≤ ....) www.acmicpc.net 이 문제 역시 알고리즘 수업에 나온 문제가 백준에 있길래 풀어보았다. 내가 아는 이집트 분수의 풀이법은 2가지다. 1. 현재 분수에서 뺄 수 있는 가장 큰 기약분수로 빼면서 구하기 2. 현재 분수 p/q를 뒤집어서 q/p로 만든 후, 이 q/p보다 큰 정수를 선택하고, 그 정수를 역을 취해 원래 분수에 빼주는 방법 2번 방법이 시간적인 측면에서 훨씬 유리하기 때문에, 2번으로 해보려다가 문제의 조건을 보고 1번 방법을 택했다. (..
