[백준] 2404 : 단위 분수로 분할 - JAVA

문제

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

2404번: 단위 분수로 분할

 

풀이

실버1문제인데 체감 난이도는 골드 1, 플레이다. 나한테는 짱어려웠다.

뭔가 백트레킹 문제라는 것은 문제를 보고 감이 왔는데 어떻게 백트레킹을 적용시킬지 매우 어려웠다.

즉, 백트레킹 함수의 매개변수를 어떻게 설정하느냐가 가장 중요한 문제였다.

 

우리는 p/q가 합이 되는 단위 분수들을 구해야한다.

즉, 우리는 백트레킹을 이용하여 단위 분수들의 합을 구해야 한다.

 

그러므로 매개변수를 다음과 같이 설정했다.

back(단위분수의 합의 분자, 단위분수 합의 분모, 만들려는 단위분수의 분모가 시작되는 숫자, 단위분수 현재 개수)

그러므로 처음 main함수에서 back함수를 호출할 때 인수를 0, 1, 1, 0으로 설정해주었다.

처음에는 단위분수의 합이 없으므로 이는 0이고 0/1과 같다. 

그러므로 위와 같이 인수를 설정해 주었다.

 

단위분수의 분모의 숫자는 start 부터 시작한다. 

기존의 단위분수의 합은 numerator / denominator 가 된다.

그리고 우리가 만드는 단위분수는 1/i가 된다.

그렇기 때문에 새로운 단위분수의 합에 대해 분모는 denominator*i가 되고 분자는 denominator + numerator*i 가 된다.

public static void back(int numerator, int denominator, int start, int depth) {
		if(p * denominator == q * numerator) {
			answer++;
			return;
		}
		if(depth == n) {
			return;
		}
		
		for(int i=start; i*denominator <= a ; i++) {
			int nn = denominator + numerator * i;
			int nd = denominator * i;
			back(nn, nd, i, depth+1);
		}
		
		
	}

 

종료조건은 매우 쉽다. 

단위 분수의 총합이 p/q일때, 단위 분수의 개수가 n일때 return 하면 된다.

 

단위 분수의 총합에 대한 분자는 numerator고 분모는 denominator다. 단위 분수의 총합과 p/q가 같다는 식을 다음과 같이 작성했다.

if(p * denominator == q * numerator) {
    answer++;
    return;
}

중고등학교 때 배웠던 것을 생각해보자. 

위의 식이 잘 기억날 것이다. 즉, 이를 이용해서 단위 분수의 총합과 p/q가 같다는 식을 만들어 주었다.

 

Q. 처음에 함수의 인수로 start라는 매개변수에 대해 1을 넣은 이유가 뭔가. 2를 넣어야 되는거 아닌가

A. 문제에서 단위 분수를 분모가 양수인 분수로 설정하였다. 따라서 1부터 넣었다.

 

코드

import java.io.*;
import java.util.*;

class Main {	
	
	static int p, q, a, n;
	static int answer = 0;
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		p = Integer.parseInt(st.nextToken());
		q = Integer.parseInt(st.nextToken());
		a = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		
		back(0, 1, 1, 0);
		
		System.out.println(answer);
	}
	
	public static void back(int numerator, int denominator, int start, int depth) {
		if(p * denominator == q * numerator) {
			answer++;
			return;
		}
		if(depth == n) {
			return;
		}
		
		for(int i=start; i*denominator <= a ; i++) {
			int nn = denominator + numerator * i;
			int nd = denominator * i;
			back(nn, nd, i, depth+1);
		}		
	}
}

 

참고로 이 문제는 내 힘으로 풀지는 못했고 구글링을 통해 매개변수만 어떻게 설정했는지 보고 풀게되었다.
이 링크를 참고했다.

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=230274
추후에 다시 풀어야 되는 문제다.