RATIO 조언 부탁드립니다.

  • sharkpc
    sharkpc

    안녕하세요~
    가입하고 처음으로 문제를 풀어보는데 잘 되지 않아 조언을 구하고자 글을 올리게 되었습니다..

    현재 PYTHON 3 으로 구현해보고 있습니다.
    방정식으로 풀어보다가 문제 자체가 이진탐색이라고 해서,
    이진탐색으로 +1%이상의 값의 근접한 값을 찾고 이를 출력해주는 방식으로 구현하였습니다.

    파이썬에서 부동소수점의 한계로 인해서 깊게 중간점을 찾지는 못하지만 정수부가 같으면 더이상 찾는것이 의미가 없을듯하여 출력하도록 하였지만 통과하지 못하고 있습니다.

    조언 부탁드립니다.^^

    import math

    testCases = int(input())

    for i in range(testCases):
    inDatas = input().split(" ")

    N = int(inDatas[0])
M = int(inDatas[1])

if (N > 1000000000) or (N < 1) or (M < 0):
   print("-1")
   continue

curPro = int((M / N)*100) / 100

if (curPro >= 0.99):
   print("-1")
   continue

curPro = curPro + 0.01
start = 1
end = 2000000000
alpha = (end + start) / 2

# Binary search를 수행하면서 start와 end의 정수부가 같으면 더이상 탐색하지 않도록 설정.
while math.ceil(end) > math.ceil(start) :        
    lastPro = ((M + alpha) / (N + alpha))

    if lastPro >= curPro:          
        end = alpha
    else:
        start = alpha

    alpha = (end + start) / 2

print (math.ceil(alpha))

    8년 전
6개의 댓글이 있습니다.
  • et16
    et16

    카테고리가 수학이라, 전 계산식으로 풀었어요.
    방정식 만들어서 이리 저리 옮겨보니 나오더라구요. ^^;


    8년 전 link
  • sharkpc
    sharkpc

    카테고리대로 풀어보고 싶었습니다ㅠ


    8년 전 link
  • et16
    et16

    제가 알고스팟에 온지 얼마 안되어서 힌트를 어디까지 드려야 할지 모르겠네요 ^^;

    탐색이나 루프는 없었구요, 노트에
    lastPro = ((M + alpha) * 100 / (N + alpha)) 에서 시작해서
    alpha = (...)형식의 계산식으로 바꿔서 적용했어요.
    한줄로 표현 가능 해요.
    lastPro 값 때문에 해매긴 했어요, ^^;
    실수 변수 사용하신 듯 한데요, 모두 정수 변수로 가능해요.

    해보시고 안되시면 수식 힌트 조금 더 드릴께요.


    8년 전 link
  • sharkpc
    sharkpc

    답변 감사합니다!
    저도 처음엔 방정식으로 했었는데
    다만 카테고리대로 이진탐색을 사용해서 풀어보고 싶었어요ㅠ


    8년 전 link
  • et16
    et16

    아!! 튜토리얼에는 수학으로 되어 있어서요,
    저도 탐색으로도 한번 해봐야 겠네요


    8년 전 link
  • free-lunch
    free-lunch

    curPro = int((M / N)*100) / 100
    여기 부분에서 M와 N에 990, 1000을 넣으면 0이 나옵니다.
    int/int를 하면 int가 나오기 때문에 원하시는 소수점 값이 아닌 대부분 0이 나올 것입니다.

    원하는 값을 나타내기 위해서는 int((M*1.0/N)*100)*1.0 / 100 이런식으로 하시거나..
    (M * 100) / N으로 하신 뒤, 99로 비교하셔도 될듯 싶습니다.


    8년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.