백준1654

·백준
이 문제를 처음 봤을 때 어떤 방식으로 풀어야 하는지 25분 정도 고민을 한 것 같다. 왜냐하면 아래와 같은 방식이나 이와 유사한 방식만 생각이 들었기 때문이다.입력받은 K[i]들을 다 더한 후 N으로 나눈다.나눈 몫을 1씩 줄여가며 각 랜선의 길이에 나눈다(2중 반복문).나눈 몫을 누적하여 N과 동일할 때까지 반복한다.이러한 풀이는 시간복잡도가 $O(n*m)$ (사실상 $O(n^2)$)이라서 풀 수 없다.해당 문제는 시간제한이 2초이고 주어진 값의 범위가 $1    결론적으로 이 문제는 이분탐색 알고리즘을$O(\log_2 n)$ 사용하면 해결된다.그러나 주의할 점이 있다. 문제 해결 시 주의사항1. 오버 플로우를 조심해라.- 이분탐색 로직 중 left와 right 변수를 더할 때 $2^{31}-1$을 ..
masjeong
'백준1654' 태그의 글 목록