[Baekjoon] 2404. 단위 분수로 분할 - python

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

2404번: 단위 분수로 분할

문제 정보

문제 유형	난이도	걸린 시간	해결 유무
백트래킹	실버1	1.2h	o

설계 방법

백트래킹

구해야 하는 타깃 분수에서 모든 경우의 수를 빼가면서 풀이함

코드

시간초과 ..

from fractions import Fraction
import sys
input = sys.stdin.readline

p, q, a, n = map(int, input().split())
target = Fraction(p, q)

def backtrack(remaining, start, depth, product): # 남은 양, 단위분수 분모, 분수갯수, 단위분수 분모 곱
    # 남은 양이 0보다 작거나, 단위분수 분모 곱이 a보다 크거나, 분수갯수가 n보다 크면 return 0
    if remaining < 0 or product > a or depth > n: 
        return 0
    # 남은 양이 0이고, 분수 개수가 n보다 작거나 같으면 return 1
    if remaining == 0 and depth <= n: 
        return 1
    count = 0
    for i in range(start, a + 1):
        unit_fraction = Fraction(1,i)
        if remaining-unit_fraction < 0 or product * i > a:
            continue
        # 1부터 a까지 돌면서 가능한 경우의 수만 count
        count += backtrack(remaining - unit_fraction, i, depth + 1, product * i) 
    return count

print(backtrack(target, 1, 0, 1))

 

정답 코드 !

from fractions import Fraction
import sys
input = sys.stdin.readline

p, q, a, n = map(int, input().split())
target = Fraction(p, q)

def backtrack(remaining, start, depth, product): 
    if remaining < 0 or product > a or depth > n: 
        return 0
    if remaining == 0 and depth <= n: 
        return 1
    count = 0
    for i in range(start, int(a / product) + 1): # 범위 수정
        unit_fraction = Fraction(1,i)
        # 남은 양 - 단위 분수가 0보다 작거나, 분모 곱이 a를 넘으면 continue
        if remaining-unit_fraction < 0 or product * i > a:
            continue
        count += backtrack(remaining - unit_fraction, i, depth + 1, product * i) 
    return count

print(backtrack(target, 1, 0, 1))

어차피 product가 a보다 크면 못 돌기 때문에 for문을 도는 범위를 (start, a+1) → (start, a//product + 1) 로 변경해 주었다

재귀도는 횟수를 줄임으로서 시간초과 극복함

++ 남은양-단위분수 0보다 작은 경우가 대부분이라 미리 처리해줌으로서 backtracking 도는 횟수 줄임 

 

근데 분명 더 좋은 풀이가 있을 것 같다

절대 1부터 a까지 도는 풀이일리 없음 .. 

메모리랑 시간이 노력이 가상해서 정답처리해준 수준

(스터디에서 다른 분들 푸신 거 보고 다시 풀어보자 .. >!)

 

시간 복잡도

O(2^n) ? O(a^n) ..?

어려웠던 점

백트래킹 풀다보면 함수 안에서 내가 돌고 있는 듯한 느낌을 받음

많은 문제 풀면서 익숙해지자 

참고

python에서 1/3+1/3이랑 1/2+1/12+1/12하면 각각 0.6666666이랑 0.6666667 이렇게 계산되어서 정확한 값을 찾을 수 없다

따라서 fractions 모듈 사용하면 좋음 (보리님 감사합니당.. ) 

1. Import the "fractions" module

from fractions import Fraction

1. Create a fraction object

Fraction(3, 4) # 3/4