[BOJ][Python]1072 풀이

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

1072번: 게임

x, y = map(int, input().split())
z = y*100//x
if z >= 99:
    print(-1)
else:
    ans = 0
    t, b = x, 0
    while b < t:
        mid = (t + b)//2
        if z < (y+mid)*100//(x+mid):
            t = mid
            ans = t
        else:
            b = mid + 1
            ans = b
    print(ans)

이번 문제는 알아두면 좋을 내용이 나왔습니다. 풀이와 함께 소개해드리면 좋을 것 같아요.

 

문제를 좀 많이 풀어보셨던 분들이라면 바로 이분 탐색으로 풀어야겠구나 하는 생각이 드셨을 것 같아 이분 탐색으로 풀이를 진행해볼까 합니다. 방정식을 세워서 풀 수도 있겠지만 단순하게 z와 z+1로 두고 풀기에는 표현되지 않는 소수의 영향이 큰 것 같아 뾰족한 수를 잘 모르겠네요. 방법을 찾으면 추가해보도록 하겠습니다.

 

늘 그렇듯 나이브한 풀이 방법을 생각해보면 이제는 게임을 할 때 마다 이기니까 (y+ans)*100/(x+ans)(이 식에 대해서도 할 말이 있습니다)를 계속 계산하면서 z와 비교해보면 되겠구나 -> 반복문 사용하면 되겠네! 하겠지만 당연히 시간초과가 납니다. x가 10억이 주어졌다고 가정하면 1씩 올려가면서 언제 1의 자리가 바뀌는지 보고 있는 건 너무 시간이 오래걸리겠죠. 아 그러면 O(N)짜리 풀이는 안되겠구나. O(1)(식 세우기))이나 O(logN)(이분 탐색)으로 풀어야겠다 하는 추론이 가능해집니다.

 

그렇다면 이제 O(logN)의 이분 탐색을 진행해봅시다. 일단은 전제 조건을 따져보죠.

1. 앞으로 진행하는 모든 게임은 승리한다.

2. 승률이 변하지 않을 경우는 -1을 출력한다.

1번 조건은 이분 탐색에서 조건문을 어떻게 짜야하는지에 대한 내용이 되겠고, 2번 조건은 z에 따른 코드의 진행을 어떻게 할지의 조건이 되겠네요. 절대 패배하지 않으니 z가 100일 때는 당연히 변하지 않을 것이고 z가 99일 때는 소수점 자리는 계속 증가할지라도 결국 100이 되지는 않을 것입니다. 따라서 z가 99보다 크거나 같다면 -1을 출력해야겠네요.

 

다음으로는 이분 탐색인데 몇 번 소개를 했던 풀이법이고 이분 탐색에 대한 모든 내용을 이 포스팅에서 설명하는 것은 분량 문제도 있어서 간단하게 짚고 넘어가면 좋을 것 같습니다. 이분 탐색은 말 그대로 탐색을 진행함에 있어 둘로 나눠가면서 진행하는 탐색 방법을 말합니다. 해가 있을 것으로 추측되는 구간을 정하고, 반으로 나눈 뒤 다시 해가 존재할 구간을 선택하는 과정을 반복합니다. 다만 언제나 사용가능한 것은 아니고 이분 탐색을 사용하기 위해서는 이분 탐색을 진행하고자 하는 값이 특정 변수에 대해 연속적일 경우 사용할 수 있습니다. 다만 알고리즘 문제를 푸는 경우는(제가 아직 다이아 이상 티어의 문제를 풀어보지 않아서 고난이도의 문제는 어떨지 모르겠지만)어떠한 조건대로 정렬이 되어 있는 경우 사용할 수 있는 탐색 방법입니다(ex. 오름차순/내림차순으로 정렬되어 있는 수열 등). 특히 이번 문제 같은 경우 음이 아닌 정수들 사이에서 z의 1의 자리가 바뀌는 가장 작은 수를 찾아야 하는 문제이니 이분 탐색을 사용하면 딱 좋겠죠. 위의 코드도 구간을 t, b로 정하고 그 중간값인 mid를 임의의 승리 횟수로 정한 다음 대입해보면서 구간을 계속해서 줄여나가는 것을 나타낸 것입니다. 그러다 t와 b가 같아지면 반복문이 종료되고 정답이 출력되는 방식이죠.

 

이번에는 위 문제를 풀면서 알아두면 좋을 것들에 대한 내용을 조금 소개해볼까 합니다. 연산 순서에서 생기는 오차가 바로 그것인데요. 많은 분들이 해당 문제의 질문에 남겨놓은 내용이라 알아두고 가면 좋을 것 같습니다.

 

위 문제를 풀면서 승률 계산을 y*100/x로 하는 경우와 y/x*100으로 하는 경우에 답이 다르게 나오는 테스트 케이스가 있습니다(정확하게는 정수 나눗셈을 사용하지 않고 실수 나눗셈을 한 뒤 추가적인 처리로 정수형으로 변경했을 때). 50 29의 입력이 주어질 경우 답은 2지만 계산을 y/x*100으로 하는 경우 1이 출력으로 나오는 문제가 있습니다. 이 오류는 나눗셈 계산 중에 생기는 소수점 오차 때문이라고 하는데요. 사실 이론적으로는 연산의 순서가 바뀌든 안바뀌든 곱셈과 나눗셈만 있기 때문에 문제가 없어야 하는게 정상이지만, 컴퓨터의 계산 과정은 산술연산 장치에서 진행되니 사람의 생각과 약간 다를 수 있겠죠.

 

좀 극단적인 예시를 위해 몫연산을 사용해보겠습니다. 예를 들어 10 9의 경우 y//x*100을 순서대로 구해보면 y//x=0이고 0*100은 0이니 z는 0이 나오는 상황이 벌어집니다. 하지만 y*100//x를 하면 90이 제대로 나오게 되죠. 오차를 극대화 하기 위해 일부러 이런 방법을 사용했지만 제가 드리고 싶은 말씀은 나눗셈 연산을 진행하면서 특히 나눠 떨어지지 않는 경우 소수점에서 오차가 생기게 되고, 이미 오차가 생긴 후에 어떤 수를 곱하는 경우에는 그 오차가 더 커지기 때문에 이런 일이 발생할 수 있다는 것이죠(줄이 없는 노트에 글을 쓸 때, 쓰는 도중에는 그다지 이상함을 못느꼈는데 다 쓰고 보면 처음에 시작했던 위치보다 같은 줄의 글자가 저 위에 올라가 있는 경우와도 비슷하겠네요). 그래서 소수점 오차가 생기지 않는 곱 연산을 먼저 진행하고 나눗셈 연산을 진행해주어야 한다는 그런 내용이 있었습니다. 예전에 악마에게 날짜가 어쩌구 하는 브론즈 문제가 있었는데 거기서도 어떤 테스트 케이스가 23.000000001 인가 하는 숫자가 나오면서 올림을 했더니 틀리게 되는 경우가 있던 것으로 기억합니다만, 자주 보이는 경우가 아니다 보니 저도 깜빡하고 있었네요.