[Python] 백준, 1072(이진 탐색)

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

1072번: 게임

 

문제가 귀엽다.

​

단원을 알고 문제를 풀면 그 자체가 힌트다. 문제를 보고 어떤 알고리즘이 쓰여야 할까 생각하는 것도 중요하다고 생각하는데, 몇몇 문제들을 보면 이건 도대체 뭘로 풀어야 하는지 감이 안 잡히는 경우가 너무 많다. 경험 부족이라 여기고 우선 해봐야지 뭐. 이 블로그는 내 복습용 노트이기도 해서, 최대한 자주 보는 것도 좋겠다. 이러다 방문자 수를 내가 먹어버리는 건 아닐까 싶다.

​

처음엔 수학적으로 접근해보려 했지만, 굳이 의미없는 일인 것 같아 시도도 안 했다. 근데, pypy3로 제출한 사람 중 가장 빠른 시간에 문제를 해결하신 분은 수학적으로 푸신듯하다.

​

문제의 초점은 두군데다. 승률은 절대 100이 나올 수 없다. 즉, 99%의 승률을 갖고 있다면 아무리 이겨도 100%를 달성할 수 없다. 또 다른 하나는 결론적으로는 너무 어렵게 생각한 것 같은데, 이진 탐색의 범위다. 첫 시도에서는 게임 횟수의 절반을 최대 범위로 잡았는데, 굳이 이럴 필요가 없던 것 같다. 어차피 절반으로 나뉘기게 한번 더 이 과정을 반복하는 건 크게 시간 복잡도에 영향을 미치지 않지 않을까?

​

# PYTHON CODE (1) - 1차 시도

def converter(x, y):
    return int(str(y / x * 100)[:2])
 
 
a, b = map(int, input().split())
n = a // 2
answer = converter(a, b)
 
 
def game(x, y):
    pl, pr = 0, n
    while pl <= pr:
        pc = (pl + pr) // 2
 
        if converter(x + pc, y + pc) > answer:
            pr = pc - 1
 
        else:
            pl = pc + 1
 
    return pr + 1
 
 
if answer == 99 or a == b:
    print(-1)
else:
    print(game(a, b))
 

​

여기서의 폐인은 크게 3가지.

 1) 복잡한 converter설정.

 2) 이진 탐색 범위 miss

 3) if문의 깔끔 치 못한 조건

 

# PYTHON CODE(2)

def converter(x, y):
    return (y * 100)//x
 
 
a, b = map(int, input().split())
answer = converter(a, b)
 
 
def game(x, y):
    pl, pr = 0, a
    while pl <= pr:
        pc = (pl + pr) // 2
 
        if converter(x + pc, y + pc) > answer:
            pr = pc - 1
 
        else:
            pl = pc + 1
 
    return pr + 1
 
 
if answer >= 99:
    print(-1)
else:
    print(game(a, b))

이진 탐색만 푸니깐 슬슬 질린다. 근데 엄청 많이 푼 것 같은데 9문제 밖에 안 풀었더라.

​

열심히살자