이분 탐색2 [백준/Python] 13706번 제곱근 풀이이분 탐색으로 양의 정수 N의 제곱근을 찾으면 됩니다. N의 길이가 800자리를 넘지 않는다는 것은 '10^800 - 1' 이 N의 최댓값이라고 볼 수 있습니다. N의 제곱근을 기준으로 이분 탐색을 할 것이기 때문에 '10^400' 을 N의 제곱근의 최댓값으로 잡고 이분 탐색을 하면 됩니다. (이보다 범위가 늘어난다 해도 이분탐색이기 때문에 탐색 속도에 큰 차이 없습니다.) 이분 탐색으로 N의 제곱근을 찾는거니까, mid의 제곱이 n 이 된다면 탐색 완료입니다. import sysn = int(sys.stdin.readline().rstrip())start = 1end = 10 ** 400while start mid ** 2: start = mid + 1 elif n 2024. 8. 8. [백준/Python] 17266번 어두운 굴다리 풀이이분 탐색을 통해 가로등의 높이를 찾아주면 됩니다. 가운데의 값(mid)이 굴다리 모든 길을 밝힐 수 있는 가로등의 높이라면 그 값을 result 변수에 저장해둔 뒤, 해당 값보다 더 작으면서 굴다리 모든 길을 밝힐 수 있는 또 다른 가로등의 높이를 찾기 위해 반복해줍니다. 그렇게 되면, 이분 탐색이 끝날 때는 result 에는 가장 값이 작으면서도 굴다리 모든 길을 밝힐 수 있는 가로등의 높이가 저장되어 있을 겁니다. 'canLight()' 함수는 가로등의 높이가 주어질 때, 해당 가로등의 높이로 굴다리 모든 길을 밝힐 수 있는 지 없는지 True, False 를 리턴해줍니다. 이 때, prev 변수는 이전 가로등이 비춘 최대 위치입니다. import sysn = int(sys.stdin.readl.. 2024. 8. 7. 이전 1 다음
