가지고 있는 랜선의 최대 갯수는 10^4개, 랜선 하나의 길이의 최대 길이는 2^31 - 1입니다. 2^31이면 대락 2*(10^9)정도 이기 때문에 12라인의 Ans의 최댓값은 (10^4) * (2*10^9) // (10^4) = 2 * (10^9) = 2000000000 이 됩니다. 하지만 while문에서는 Ans를 1씩 감소하고 돌아가기 때문에 이렇게 큰 Ans값을 해당 조건 까지(17라인) 맞추지 못하고 시간 초과가 발생하게 됩니다.
반면 "middle = (1 + max(K_cm))//2 방식은 최소=1, 최대=가장 긴 랜선의 길이로 두고 최소>최대가 될 때 까지 탐색을 진행합니다. 마찬가지로 가장 긴 랜선의 길이의 최대값은 (2^31)-1이지만 최소 및 최대값을 한 칸 씩 이동하는 것이 아닌 매 while문 마다 최소, 최대 중 하나가 조건에 따라 가운데로 건너띄기 때문에 시간 안에 문제를 해결할 수 있게 됩니다. 어림잡아 계산해 보면 log2(2*31) = 31 정도 되겠군요.
이렇게 정렬되어 있는 배열 혹은 구간(ex: 1 ~ 가장 긴 랜선의 길이)이 정해져 있고 해당 구간 사이의 값을 빠른 시간 안에 찾는다고 할 때 사용하는 알고리즘이 이분 탐색이고, 이 문제처럼 근사값을 찾는 알고리즘을 매개변수 탐색이라고 합니다.(N개 보다 더 많이 만들어도 된다는 조건이 붙어있기 때문입니다.)
hsj5972 1년 전
middle = (1 + max(K_cm))//2 방식으로 하는 경우랑 제가 쓴 코드랑 처리시간이 많이 차이가 나나요?
왜 시간초과가 발생하는지 잘 모르겠습니다.
조언 주시면 감사하겠습니다~!