[BOJ] 1072 두 배열의 합 - python

2143번: 두 배열의 합

2143번: 두 배열의 합

풀이

부동소수점 문제 때문에 int(Y/X100)으로 풀면 안되고, int((Y100)/X) 로 풀어야 한다. /는 소수점까지, //는 몫, %는 나머지! while문 다 돌리면서로 해봤지만 X무시무시하게 크기 때문에, 추가로 이긴 횟수를 변수로 이진탐색을 한다. start,end = 0,1000000000로 설정한다. start≤end 일 때까지 수행하며, start>end가 되었을 때 mid값은 start,end와 동일하다. 새로운 승률이 기존 승률보다 크면 → answer를 갱신하고 변수를 줄여준다. (end = mid-1) 또 승률이 올랐을 때 가장 작은 값을 구해야 하므로 answer를 min을 이용하여 갱신한다. 새로운 승률이 기존 승률보다 작으면 → 변수를 늘려준다. (start = mid +1) 이진탐색이 완료된 후 승률이 올랐을 경우 중 가장 작은 값인 answer를 출력한다.

틀린 코드

import sys
def input():
    return sys.stdin.readline().rstrip()

#print(int(47/53*100))

X,Y = map(int,input().split(" ")) # X:게임횟수, Y:이긴게임

Z = int(Y/X *100)
initZ = Z
#print(Z)

answer = 0
if X == Y:
    print(-1)
    exit()

#무조건 이기니까 다 돌려보고 변하는 순간 캐치하기 -> 시간이 될까?
while True:
    Y += 1
    X += 1
    answer += 1
    Z = int((Y)/(X)*100)
    if Z > initZ:
        break

print(answer)

최종 코드

import sys
def input():
    return sys.stdin.readline().rstrip()

X,Y = map(int,input().split(" ")) # X:게임횟수, Y:이긴게임

#파이썬에서 부동소수점 문제 때문에 int((Y/X)*100)으로는 정확한 답이 나오지 않는다.
Z = int((Y*100/X)) 
initZ = Z

if Z >= 99:
    print(-1)
    exit()

#추가로 이긴 횟수를 변수로 이분탐색 시작

start,end,newZ = 0, 1000000000, Z
answer = end

#start,end가 같아질 때 까지 수행(->이전에 생성된 mid는 start,end값과 동일한 값)
#start > end면 종료
while start <= end:
    mid = (start+end) // 2
    newZ = (Y+mid)*100 // (X+mid)

    if newZ > Z:
        answer = min(mid,answer)
        end = mid - 1
    else:
        start = mid + 1

print(answer)

얻어가는 것

• 파이썬의 부동소수점 오차 문제→ 해결 방법
• import decimal decimal.Decimal('0.1') * 3 == decimal.Decimal('0.3') >>> True
• #if문 사용시 부동소수점 때문에 오차가 생길 수 있다. 0.1 * 3 == 0.3 >>> False
• 3항연산자
• print(answer if answer > 0 else -1)

느낀점

"211201"

소요 시간 : 1h

• 이분탐색을 이용하리라고는 생각지도 못한 곳에서 이분탐색이 나와서 놀랐다
• X가 대빵크다면 정렬되어있지 않아도, 이분탐색으로 사용할 수 있는 변수가 존재하는지 확인해보자!