[BOJ] 2404. 단위 분수로 분할

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

2404번: 단위 분수로 분할

풀이

좀 많이 어려웠다. 시간 제한이나 범위로 봐서는 완탐으로 돌리는게 맞는데 어딜 어떻게 잡고 돌려야 할지 감이 오지 않았다.

이것만 떠올리면 문제에 접근하는데 감이 확 온다.

a/b=c/d <-> ac=bd

즉 a/b를 주어진 p/q라고 생각하고, c/d를 만들어진 단위 분수라고 생각했을 때 p*d==q*c를 만족하는 경우를 세면 되는 것이다.

 

코드

package backtracking;

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

public class boj_2404_단위분수로분할 {

    static int p, q, a, n, ans = 0;

    static void backTracking(int nume, int deno, int start, int cnt) {
        if (deno * p == nume * q) {
            ans++;
            return;
        }

        if (cnt == n) {
            return;
        }

        for (int i = start; i * deno <= a; i++) {
            int nxtNume = deno + nume * i;
            int nxtDeno = deno * i;
            backTracking(nxtNume, nxtDeno, i, cnt + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        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());

        backTracking(0, 1, 1, 0);

        System.out.println(ans);
    }
}