2023. 11. 18. 10:55ㆍ알고리즘
♣ 시도1. 무식하게 수학식으로 도전!
더 게임한 횟수를 m으로 잡고, m을 1씩 늘려가면서 조건에 해당하는지 체크하는 방법이다. 보다시피 수학 식도 지저분하고 쓸데없는 부분까지 들어가있다. ( m을 1부터 시작하는 거니까 z+2와는 굳이 비교할 필요가 없다. )
시간제한이 없으면 정답 처리되겠지만 당연히 시간 초과로 나가리당했다.
♣ 지저분한 수학식을 함수로 정리해서 도전!
지난 번 스터디에서 그냥 수학식을 푸는 것보다 함수를 정의한 후 함수를 사용하는 게 사용되는 시간을 줄일 수 있다는 것을 배웠다. 그래서 이번에는 지저분한 수학식을 함수로 정의한 후 사용했다.
여전히 시간을 초과해서 실패!
♣ 이분탐색을 이용하여 도전!
본 문제는 이분탐색을 이용하여 해결해야 한다고 한다. 게임을 더 할 수 있는 최소 횟수와 최대 횟수를 범위로 두고, 반씩 잘라가면서 중간값을 게임을 추가로 한 횟수이자 추가로 이긴 횟수로 했을 때 승률이 z+1이 되는지 확인한다. 이 때 승률이 z+1보다 작으면 더 많이 게임을 해야 하므로 중간값을 최소 횟수로 설정한다. 승률이 z+1이 되면 게임을 더 적게 해도 승률이 z+1이 되는 횟수를 구해야 하므로 중간값을 최대 횟수로 설정한다. 이를 최소 횟수와 최대횟수가 같아질 때까지, 즉 더이상 범위를 반으로 나눌 수 없을 때까지 반복한다.
또한 승률이 99%이면 아무리 게임을 더 많이 해도 100%는 될 수 없기 때문에(이미 앞에서 몇 개 틀려서 99%가 된 것이니까) -1을 출력한다.
S: 추가 게임 최소 횟수
L: 추가 게임 최대 횟수
'알고리즘' 카테고리의 다른 글
| 백준 1541번 잃어버린 괄호 (1) | 2023.12.06 |
|---|---|
| 백준 알고리즘 11659번(구간합 구하기) (1) | 2023.12.04 |
| 백준 1213번(팰린드롬 만들기) (1) | 2023.11.29 |
| 백준 1929 (1) | 2023.11.16 |
| 백준 알고리즘 1920번 (0) | 2023.11.08 |