99클럽 코테 스터디 1일차 TIL, 부등식

취업과 무관하게 알고리즘 활용 능력이 녹스는 거 같아 덜 녹슬고자 코딩 스터디에 참여하게 됐다! 두구두구

백준 1072 게임

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

• 부등식, 조각함수
• 풀이 방식
  • $z = y * 100.0 / x$ 이고 $w$회 게임을 더 하되 $z$가 변하려면
    $z+1≤(y+w)*100.0/(x+w)$이어야 한다.
  • 부등식을 구하려는 $w$에 대하여 정리하면
    $z>99$일 때 $w > \frac{(z+1)x-100y}{99-z}$가 된다.
  • 이미 진 전적이 있을 때 승률 100%가 될 수 없고, 승률 100%일 때도 $z$가 변할 수 없기 때문에 $z=99, 100$일 때 답은 -1이다.
• 오늘의 회고
  • 자세히 고민하기도 전에 힌트를 봤다가 이분탐색으로 풀어야 한다는 고정관념이 생겨 버려서 오래 걸렸다. 처음부터 요령 피우지 않고 풀어 나가야겠다.
  • 부등식 정리가 잘 안됐다... 분모로 곱하고 나누는 것 뿐인데도.. 머리가 굳었나보다

파이썬 코드

x, y = map(int, input().split())
z = int(y * 100.0 // x)
if z >= 99:
    print(-1)
else:
    w = ((z + 1) * x - 100.0 * y) / (99 - z)
    if int(w) == w:
        print(int(w))
    else:
        print(int(w) + 1)