★[python_파이썬_pass]백준_1072번_게임_이분탐색_풀이

공부하는허딩크 : https://www.youtube.com/live/5TQ9cxVHNk0?feature=shared

처음 이진탐색을 해결할때 대략적인 형태를 보고 처음 문제를 접했다... 근데 역시나 활용하기에는 내 실력이 많이 부족했다.
 
<첫번째 시도 : 정답 근처에도 가지 못함>
방향은 그래도 근접하게 접근을 했다.
1. 일단 승률 Z를 구한다.
2. data를 Y부터 X까지 나오게 리스트를 만든다.
3. Z(target)과 data를 함수 요소로 넣어서 실행한다.
4. mid를 구한다.
5. 신규 x, y를 구한 후 다시 승률을 만들어서 기존 Z와 비교한다.
   ㄴ 다르면 end = mid - 1
   ㄴ 같으면 start = mid + 1
그런데 답이 이상하게 나온다.....

import sys

input = sys.stdin.readline

X, Y = map(int, input().split())

Z = int(Y / X * 100)

 

#이진탐색 함수

def bin_check(target, data):

    start = 0

    end = len(data) - 1

   

    while start <= end:

        mid = (start + end) // 2

        x = data[end] + mid

        y = data[start] + mid

        if data[start] == data[end]:

            print(-1)

            return

        elif Z != average(x, y):

            end = mid - 1

        else:

            start = mid + 1

#평균 함수

def average(x, y):

    return int(y / x * 100)

print(bin_check(Z, list(range(Y, X + 1))))

 
<Ghat_gpt도움>
내가 작성한 코드와 비슷한 방향으로 도움을 받았다.
※ Z = int(Y / X * 100)을 하면 틀리다고 나오고 / Z = (Y * 100) // X를 해야 정상적으로 나온다.
 아직 이진탐색 감이 정확히 안들어 온다. 될때까지 때려 박아야지.

import sys

input = sys.stdin.readline

X, Y = map(int, input().split())

Z = (Y * 100) // X

def bin_check(X, Y, Z):

    start = 1

    end = 1000000000

    result = -1

   

    while start <= end:

        mid = (start + end) // 2

        new_X = X + mid

        new_Y = Y + mid

        new_Z = (new_Y * 100) // new_X

       

        if new_Z > Z:

            result = mid

            end = mid - 1

        else:

            start = mid + 1

    return result

print(bin_check(X, Y, Z))

 

<스터디원 코드>

import sys

sys.setrecursionlimit(10**6)

input = sys.stdin.readline

x, y = map(int, input().split())

def binary_find(start, end):

   

    mid = (start + end)//2

    if start == end:

        print(start)

        return

    if (y+mid)*100 // (x+mid) > (y * 100) // x:

        binary_find(start, mid)

    else:

        binary_find(mid+1, end)

if (y/x)*100 >= 99:

    print(-1)

else:

    binary_find(0, x)

    #x요소 대신 1000000000도 괜찮음

 

 

<추가 복습>

아래의 코드는 일단 메모리초과 내가봐도 무리가 있다.

일단 10억개의 리스트를 만들고 나서 시작을 해야하니까 안봐도 메모리든 시간이든 초과될 것 같다.

import sys

input = sys.stdin.readline

X, Y = map(int, input().split())

Z = (Y * 100) // X #Y/X *100이 안되는 부분 리뷰 필요

#Binary Search

def BS(arr):

    start, end = 0, len(arr) - 1

    cnt = -1

   

    while start <= end:

        mid = (start + end) // 2

        new_X = X + arr[mid]

        new_Y = Y + arr[mid]

        new_Z = (new_Y * 100) // new_X

       

        if new_Z > Z:

            cnt = mid

            end = mid - 1

           

    return cnt

print(BS(list(range(1, 1000000000))))

 

이게 맞는 것 같다.

아래 else조건이 없으면 시간초과가 뜬다. 일단 파이썬에서는 답이 나오는데 X., Y값이 같을 경우 무한루프에 빠진다.

new_Z와 Z가 같을 경우 start를 계속해서 mid + 1로 해줘야 마지막에 -1이 출력될 수 있다.

start, end, mid =  1 1000000000 500000000
new_X, new_Y, new_Z =  500000047 500000047 100
start, end, mid =  1 1000000000 500000000
new_X, new_Y, new_Z =  500000047 500000047 100

        # else:

        #     start = mid + 1

import sys

input = sys.stdin.readline

X, Y = map(int, input().split())

Z = (Y * 100) // X #Y/X *100이 안되는 부분 리뷰 필요

#Binary Search

def BS():

    start, end = 0, 1000000000

    cnt = -1

   

    while start <= end:

        mid = (start + end) // 2

        new_X = X + mid

        new_Y = Y + mid

        new_Z = (new_Y * 100) // new_X

        print("start, end, mid = ", start, end, mid)

        print("new_X, new_Y, new_Z = ", new_X, new_Y, new_Z)

       

        if new_Z > Z:

            cnt = mid

            end = mid - 1

        else:

            start = mid + 1

           

    return cnt

print(BS())

 

<코드 풀이.... 잘 고민해보자!!!!!>

1. 출력값은 아래와 같다.start를 1로 해도 상관 없다.

2. start는 변함 없이 10억에서 시작해서 mid가 5억대 / 2.5억대 / 1.25억대.... 계속 이렇게 줄어들면서 승률을 구하고 Z와 비교한다.

3. 마지막 start <= end조건까지

10 8
start, end, mid =  0 1000000000 500000000
new_X, new_Y, new_Z =  500000010 500000008 99
start, end, mid =  0 499999999 249999999
new_X, new_Y, new_Z =  250000009 250000007 99
start, end, mid =  0 249999998 124999999
new_X, new_Y, new_Z =  125000009 125000007 99
start, end, mid =  0 124999998 62499999
new_X, new_Y, new_Z =  62500009 62500007 99
start, end, mid =  0 62499998 31249999
new_X, new_Y, new_Z =  31250009 31250007 99
start, end, mid =  0 31249998 15624999
new_X, new_Y, new_Z =  15625009 15625007 99
start, end, mid =  0 15624998 7812499
new_X, new_Y, new_Z =  7812509 7812507 99
start, end, mid =  0 7812498 3906249
new_X, new_Y, new_Z =  3906259 3906257 99
start, end, mid =  0 3906248 1953124
new_X, new_Y, new_Z =  1953134 1953132 99
start, end, mid =  0 1953123 976561
new_X, new_Y, new_Z =  976571 976569 99
start, end, mid =  0 976560 488280
new_X, new_Y, new_Z =  488290 488288 99
start, end, mid =  0 488279 244139
new_X, new_Y, new_Z =  244149 244147 99
start, end, mid =  0 244138 122069
new_X, new_Y, new_Z =  122079 122077 99
start, end, mid =  0 122068 61034
new_X, new_Y, new_Z =  61044 61042 99
start, end, mid =  0 61033 30516
new_X, new_Y, new_Z =  30526 30524 99
start, end, mid =  0 30515 15257
new_X, new_Y, new_Z =  15267 15265 99
start, end, mid =  0 15256 7628
new_X, new_Y, new_Z =  7638 7636 99
start, end, mid =  0 7627 3813
new_X, new_Y, new_Z =  3823 3821 99
start, end, mid =  0 3812 1906
new_X, new_Y, new_Z =  1916 1914 99
start, end, mid =  0 1905 952
new_X, new_Y, new_Z =  962 960 99
start, end, mid =  0 951 475
new_X, new_Y, new_Z =  485 483 99
start, end, mid =  0 474 237
new_X, new_Y, new_Z =  247 245 99
start, end, mid =  0 236 118
new_X, new_Y, new_Z =  128 126 98
start, end, mid =  0 117 58
new_X, new_Y, new_Z =  68 66 97
start, end, mid =  0 57 28
new_X, new_Y, new_Z =  38 36 94
start, end, mid =  0 27 13
new_X, new_Y, new_Z =  23 21 91
start, end, mid =  0 12 6
new_X, new_Y, new_Z =  16 14 87
start, end, mid =  0 5 2
new_X, new_Y, new_Z =  12 10 83
start, end, mid =  0 1 0
new_X, new_Y, new_Z =  10 8 80
start, end, mid =  1 1 1
new_X, new_Y, new_Z =  11 9 81
1

<start룰 1로 했을 경우_마지막에 조금 차이가 있다.>

10 8
start, end, mid =  1 1000000000 500000000
new_X, new_Y, new_Z =  500000010 500000008 99
start, end, mid =  1 499999999 250000000
new_X, new_Y, new_Z =  250000010 250000008 99
start, end, mid =  1 249999999 125000000
new_X, new_Y, new_Z =  125000010 125000008 99
start, end, mid =  1 124999999 62500000
new_X, new_Y, new_Z =  62500010 62500008 99
start, end, mid =  1 62499999 31250000
new_X, new_Y, new_Z =  31250010 31250008 99
start, end, mid =  1 31249999 15625000
new_X, new_Y, new_Z =  15625010 15625008 99
start, end, mid =  1 15624999 7812500
new_X, new_Y, new_Z =  7812510 7812508 99
start, end, mid =  1 7812499 3906250
new_X, new_Y, new_Z =  3906260 3906258 99
start, end, mid =  1 3906249 1953125
new_X, new_Y, new_Z =  1953135 1953133 99
start, end, mid =  1 1953124 976562
new_X, new_Y, new_Z =  976572 976570 99
start, end, mid =  1 976561 488281
new_X, new_Y, new_Z =  488291 488289 99
start, end, mid =  1 488280 244140
new_X, new_Y, new_Z =  244150 244148 99
start, end, mid =  1 244139 122070
new_X, new_Y, new_Z =  122080 122078 99
start, end, mid =  1 122069 61035
new_X, new_Y, new_Z =  61045 61043 99
start, end, mid =  1 61034 30517
new_X, new_Y, new_Z =  30527 30525 99
start, end, mid =  1 30516 15258
new_X, new_Y, new_Z =  15268 15266 99
start, end, mid =  1 15257 7629
new_X, new_Y, new_Z =  7639 7637 99
start, end, mid =  1 7628 3814
new_X, new_Y, new_Z =  3824 3822 99
start, end, mid =  1 3813 1907
new_X, new_Y, new_Z =  1917 1915 99
start, end, mid =  1 1906 953
new_X, new_Y, new_Z =  963 961 99
start, end, mid =  1 952 476
new_X, new_Y, new_Z =  486 484 99
start, end, mid =  1 475 238
new_X, new_Y, new_Z =  248 246 99
start, end, mid =  1 237 119
new_X, new_Y, new_Z =  129 127 98
start, end, mid =  1 118 59
new_X, new_Y, new_Z =  69 67 97
start, end, mid =  1 58 29
new_X, new_Y, new_Z =  39 37 94
start, end, mid =  1 28 14
new_X, new_Y, new_Z =  24 22 91
start, end, mid =  1 13 7
new_X, new_Y, new_Z =  17 15 88
start, end, mid =  1 6 3
new_X, new_Y, new_Z =  13 11 84
start, end, mid =  1 2 1
new_X, new_Y, new_Z =  11 9 81
1

 

<수학 법칙 : 다른 결과값을 찾아 달라고 하는데 절대 못찾는데...... 일단 외워두자.>

Z = int(Y / X * 100)와 Z = (Y * 100) // X는 언뜻 보면 같은 결과를 내야 할 것 같지만, 실제로는 다른 결과를 내는 경우가 있습니다. 이는 파이썬의 소수점 연산과 정수 나눗셈의 차이 때문에 발생합니다. 각각의 방식이 어떻게 작동하는지 살펴보겠습니다.

1. Z = int(Y / X * 100)

이 식은 다음과 같이 단계별로 연산됩니다:

1. Y / X: 먼저 Y를 X로 나눕니다. 이때 결과는 부동 소수점(float) 값이 됩니다.
2. Y / X * 100: 이 부동 소수점 값에 100을 곱합니다. 이 과정에서도 여전히 결과는 부동 소수점 값입니다.
3. int(...): 부동 소수점 값을 int로 변환하여 소수점 아래 자리를 잘라냅니다.

문제점:

• 부동 소수점 연산의 정확도 문제로 인해 실제 결과가 정확히 떨어지지 않을 수 있습니다. 예를 들어, Y / X의 값이 0.33333... 같은 무한 소수인 경우, Y / X * 100의 값은 33.333...이 되며, int()로 변환하면 33이 됩니다.
• 부동 소수점 연산에서의 오차로 인해 의도하지 않은 결과가 나올 수 있습니다.

2. Z = (Y * 100) // X

이 식은 다음과 같이 단계별로 연산됩니다:

1. Y * 100: 먼저 Y에 100을 곱합니다. 이 결과는 정수(int) 입니다.
2. (Y * 100) // X: 그 다음에 X로 정수 나눗셈(몫 연산)을 수행합니다. 이 연산은 정수형 나눗셈이므로 소수점 아래 자리를 무시하고, 정확한 정수 결과를 반환합니다.

장점:

• 모든 연산이 정수형으로 수행되므로 부동 소수점 연산의 오차가 없습니다.
• 결과가 int로 정확하게 나오므로 예상한 값이 출력됩니다.