Problem Set/완전탐색
[BOJ] 2404. 단위 분수로 분할
https://www.acmicpc.net/problem/2404 2404번: 단위 분수로 분할 첫째 줄에 양의 정수 p, q, a, n이 입력된다. (1 ≤ p, q ≤ 800, 1 ≤ a ≤ 12000, 1 ≤ n ≤ 7) www.acmicpc.net 풀이 좀 많이 어려웠다. 시간 제한이나 범위로 봐서는 완탐으로 돌리는게 맞는데 어딜 어떻게 잡고 돌려야 할지 감이 오지 않았다. 이것만 떠올리면 문제에 접근하는데 감이 확 온다. a/b=c/d ac=bd 즉 a/b를 주어진 p/q라고 생각하고, c/d를 만들어진 단위 분수라고 생각했을 때 p*d==q*c를 만족하는 경우를 세면 되는 것이다. 코드 package backtracking; import java.util.*; import java.io.*; ..
