BOJ 2404 단위 분수로 분할

분자가 1이고 분모가 양수인 분수를 단위 분수라고 하고 p/q를 단위분수의 합으로 나타내었을 때 p/q를 단위분수로 분할했다고 말한다.
입력으로 p, q, a, n이 주어지면 분수 p/q를 n개 이하의 단위 분수의 합으로 나타내는 경우의 수를 구하는 것이 문제인데, 이 때 분할을 이루는 분모의 곱이 a이하여야 한다.

dp 느낌이 든다.
d[p][q][a][n]= p/q를 n개 이하의 (분할을 이루는 분모의 곱이 a이하이면서 ) n개 이하의 단위 분수의 합으로 나타내는 경우의 수
로 하면 d[p][q][a][n]=SUM( d[np][nq][a/aq][n-1] )... 대충 이런 식으로.. 하지만, 배열을 d[p][q][a][n]으로 설정할 경우 메모리 초과가 분명하다.

a가 무려 최대 12000인데 a를 뺄 수 있을까? a를 그냥 parameter로 넘겨주면 어떨까? 음 안될 것 같다. p, q, n이 같아도 a가 다르면 달라질 수 밖에 없다... 그렇다면 a를 parameter로 보내되, a보다 더 작은 값으로 a를 대체할 수는 없을까? 음... 아니면 p나, q중 하나만 줄여도 메모리 초과는 안 날텐데, p나 q중 하나를 없앨 수 있을까?

방금 맞은 사람 목록을 봤는데, 메모리뿐만 아니라 코드 길이도 매우 짧은 편이다. 비록 맞은 사람이 2명밖에 없긴하지만... 음... dp가 아닌가? 다르게 생각해 봐야겠다.

n이 최대 7이니까 일일이 다 해보는 방식은 어떨까?
좀 더 고민을 해 봤는데, 분할을 이루는 분모의 곱이 a이하여야 하므로 이 말은 즉, 분할을 이루는 분모의 곱이 a이하의 어떤 수가 된다는 것으로도 볼 수 있다. 예를 들어 a가 12000이고, n이 7이면 1부터 12000까지 모든 수를 각각 분할을 이루는 분모의 곱으로 보면서 각 경우에 대해서 n은 1부터 7까지 보면서 단위 분수의 조합을 구해서 합해보고
비교할 땐 그 합한 값이 p/q와 p%q와 같은지 살펴보고 같으면 count해주는 식으로... 좀 복잡할 것 같지만 한 번 구현해 봐야겠다. 아... 이렇게 하면 단위 분수의 조합을 구하는데 시간이 너무 많이 걸린다.

음 일단 넘어가고.. 백준님의 해설 강의를 들어야겠다.

백트래킹... 재귀를 쓰려면 문제가 재귀적인 형태를 띄는지 봐야한다.
non decreasing 으로 뽑으면 중복되지 않게 뽑음.(조합)