백준 1072 문제 풀이
문제
김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.
이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.
게임 기록은 다음과 같이 생겼다.
게임 횟수 : X
이긴 게임 : Y (Z%)
Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.
X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.
문제 해석하기_ 초기버전
- 게임 횟수와 이긴 횟수 입력 받기
- X,Y를 가지고 승률 Z만들어내기
- y/x *100 하면 승률 퍼센트 값나옴 ⇒ 소수점 없애야됨
- trunc()함수를 사용하면 소수점 아래 숫자 버릴 수 있음
- y*100//x 로 코드 단순화하기
- while 문으로 돌려서 몇판을 더 해야 승률이 변하는 지 구하기
위와 같이 일단 문제를 어떻게 풀어나가야 할 지 정해주었다. 이 과정에서 승률을 만들어내는 다양한 방안에 대해 생각하고 while문을 이용해서 문제를 해결하려고 했다.
하지만, 중간중간 빼먹은 조건들과 여러 문제들로 인해서 시간 초과라는 결과를 얻었다.
x,y = map(int, input().split())
z = y*100//x
changeZ = z
cnt=x
while changeZ <= z:
x+=1
changeZ = y*100//x
print(x-cnt)[문제점]
- 형택이는 이제 앞으로의 모든 게임에서 지지 않는다. 그렇기 때문에 이긴 횟수에 이후의 게임 횟수를 추가해줘야 하는 것이다.
=> x가 증가하는 만큼 y도 증가시켜줘야 하는 정말 기본적인 부분인데 이걸 생각하지 못했다..... - 시간 초과가 일어난다는 건 알고리즘에 대해서 생각해야 한다는 것인데 이진 탐색에 대해서 생각하지 못했다.
문제 해석하기_최종버전
- 게임 횟수와 이긴 횟수 입력 받기
- X,Y를 가지고 승률 Z만들어내기
- y*100//x 로 코드 단순화하기
- 이진 탐색을 이용해서 mid를 구하고, 해당 mid에 값을 증가, 감소 시키면서 최소의 게임 횟수를 구하기
x, y = map(int, input().split())
z = y * 100 // x
left, right = 1, x
result = -1
while left <= right:
mid = (left + right) // 2
new_z = (y + mid) * 100 // (x + mid)
if new_z > z:
result = mid
right = mid - 1
else:
left = mid + 1
print(result)이진 탐색이란?
이진탐색이란?
정렬된 배열이나 탐색 범위 내에서 원하는 값을 빠르게 찾는 알고리즘이다.
- 정렬된 리스트에서만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때 마다 검색 범위가 절반 씩 줄어들기 때문에 속도가 훨씬 빨라진다는 것을 알 수 있다.
- 이진 탐색은 배열을 중간값을 기준으로 둘로 나누어 탐색 범위를 줄어나가는 방식으로 작동한다.
- 시간 복잡도가 O(log N)으로 매우 효율적이다.
이진탐색의 기본 원리
- 탐색 범위의 중간값을 찾는다
- 중간값과 목표 값을 비교한다
- 중간값이 목표 값보다 크다면 왼쪽 절반에서 다시 중간값을 찾는다
- 중간값이 목표 값보다 작다면 오른쪽 절반에서 다시 중간값을 찾는다
- 이 과정을 목표 값을 찾거나 탐색 범위가 없어질 때까지 반복한다
오늘의 회고
항해99의 1일 1코테를 시작하면서 비기너와 미들러 문제 중 어떤 것을 선택할지 고민이 많았다. 과연 내가 미들러 문제를 풀어낼 수 있을지 걱정이 컸지만, 이번 문제를 보면서 비록 시간 초과가 발생하긴 했어도 문제를 해석하고 시간 내에 풀이를 진행할 수 있었다는 점에서 그동안의 성장이 느껴졌다.
비록 1일차에 불과하지만, 오늘을 계기로 더욱 열심히 공부해 마지막에는 문제를 빠르게 해석하고 정확하게 해결할 수 있는 능력을 갖추고 싶다는 다짐을 하게 되었다. 앞으로 매일 조금씩이라도 발전하는 모습을 기대하며 꾸준히 노력하고자 한다!
