[백준] S1 4587 이집트 분수 (java)

https://www.acmicpc.net/problem/4587

4587번: 이집트 분수

 

풀이

 

1) M = 0 && N = 0 이 나올때 까지 반복문을 돈다. (M : 분자, N : 분모)

2) 만약 분자(M)가 1이 아닐경우 반복문을 돌며 nextN을 찾아야 한다.

2-0) 다음 단위 분수의 후보 nextN 은 N/M(올림) 이다.

2-1) 이 때 M/N - 1/nextN을 해서 약분해야한다.

2-2) 약분을 하기 위해서 최소 공배수를 알아야한다. (다른 방법이 있을 수도 있다.)

2-3) 근데 최소 공배수를 알기 위해서는, 최대 공약수를 알아야한다.

2-4) 최대 공약수는 유클리드 호제법을 통해 얻는다.

2-5) 최대 공약수로 최소 공배수를 얻고 약분을 진행한다.

2-6) 만약 약분해서 나온 분모가 1000000 보다 크면 안된다. 이때 nextN을 1 더한다.

3) 2-1) 부터 다시 반복해서 적합한 nextN을 찾을 경우 nextN을 출력하고 N과 M을 초기화 한다.

4) while문을 탈출하면 분자(M)이 1이라는 의미이다. 마지막 분모 (N)를 출력하고 유종의 미를 거두자.

 

주의사항

 

1) 머리 빠개짐

2) int로 진행할 경우 최소 공배수를 구하는 과정에서 int의 범위를 초과하게 된다. long으로 하자.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

public class BJ_S1_4587_이집트분수 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static long M,N;
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		while(true) {
			tokens = new StringTokenizer(input.readLine());
			M = Integer.parseInt(tokens.nextToken());
			N = Integer.parseInt(tokens.nextToken());

			// 1. 0 0 이 나오면 종료
			if(M == 0 && N == 0) break;
			
			// 2. 다음 단위 분수의 분모를 정해야 함
			while(M!=1) {
				int nextN = (int) Math.ceil((double) N/M);
				while(true) { // 단위 분수의 분모가 1000000보다 크거나 같으면 nextN을 1씩 증가
					// N과 nextN의 최소 공배수가 분모이다.
					// 최소 공배수는 N * nextN / 최대 공약수이다.
					// 따라서 최대 공약수를 먼저 구한다.
					long gcd = getGcd(N, nextN);
					
					long lcm = N * nextN / gcd;
					
					long newM1 = (lcm/N)*M;
					long newM2 = lcm/nextN;
					long newM = newM1 - newM2;
					
					// 새로나온 분자와 분모를 약분해서 분모가 1000000이 넘지 않아야 한다.
					// 약분은 분자 분모의 최대공약수로 나눌 거임.
					gcd = getGcd(newM, lcm);
					newM = newM/gcd;
					lcm = lcm/gcd;
					if(lcm >= 1000000) {
						nextN++;
					}else {
						System.out.print(nextN+" ");
						N = lcm;
						M = newM;
						break;
					}
				}
			}
			System.out.println(N+" ");
		}
	}

	private static long getGcd(long newM, long lcm) {
		long temp = 0;
		while(lcm>0) {
			temp = newM;
			newM = lcm;
			lcm = temp%lcm;
		}
		return newM;
	}

	static String src =
			"3 999983\r\n" + 
			"0 0";
}

 

후기

 

 수학문제가 싫은 이유이다. 솔직히 골드 이상의 난이도로 바뀌어도 될것같다.