문제를 잘 보면 나눠줄 수 있는 "최대" 길이이므로 만족하는 숫자들의 범위 중 최댓값을 출력해주는 것이다. 따라서 이분탐색의 upper_bound를 활용해주면 된다. Upper_bound의 대략적인 skeleton code는 다음과 같다. // Upper_bound (이분탐색에서의 상계를 구하는 방법) int start = 0; int end = vector_container.size(); while (start M >> N; vector data_store; for(int i = 0; i > temp; data_store.push_back(temp); } sort(data_..

전형적인 이분탐색의 lower_bound 형태이다. 전체적인 스켈레톤은 다음과 같다. 자세한 설명은 viyoung.tistory.com/77?category=284521 참고 // Lower_bound (이분탐색에서의 하계를 구하는 방법) int start = 0; int end = vector_container.size(); while (start < end){ mid = (start + end) / 2; if(card[mid] < compare_value){ start = mid + 1; } else{ end = mid; } } 사실 이 문제는 오버 플로우 때문에 개고생했다.. 처음에는 end값을 리터럴로 잡으려고 하다가 계속 틀려서 input값을 기준으로 최댓값을 보정하니까 맞았다. (생각보다 숫자..

이분탐색 (Binary search) 이분탐색은 결과적으로 나오는 index의 값을 기준으로 upper_bound와 lower_bound로 나뉜다. 단,이분탐색으로 접근하기 위해서는, 데이터가 연속적으로 이어져있어야 하기때문에 반드시 sorting을 하고 나서 진행해야 한다. 일반적으로 중복되는 수가 없는 경우 중간값이 compare하는 값보다 작을 때는, start부터 mid값까지의 값은 compare하는 값보다 무조건 작을 수 밖에 없으므로 판단해야하는 범위는 (mid + 1, end)로 이동하게 된다. 반면에, compare하는 값보다 클 때는, mid부터 end까지의 값은 compare하는 값보다 무조건 클 수 밖에 없으므로 판단해야하는 범위는 (start, mid -1)로 이동하게 된다. 만약,..

이 문제에서 가장 중요한 지점은, 입출력이 최대 200000 까지 되므로, 빠른 입출력을 활용하여 시간을 출여야 한다. 왜 그렇게 해야하는지에 대해서는 입출력 스트림 관련해서 상당히 복잡하므로, 실력을 키우기 전까지는 그냥 받아들이고 쓰는 것으로 하자. 방법은 다음과 같다. 메인함수에 해당 내용을 최상단에 쓰면 된다. ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 단, 이 방법을 쓰는 경우에는 getchar 같은 것들을 못쓴다는 점은 유의해야 한다. 추가적으로 이 문제의 경우에는, 존재하는지 아닌지만 판단해주면 되므로 정렬 후에 이분탐색으로 판단하는 것이 쉽다. 해당하는 알고리즘으로 코드를 구현하면 다음과 같다. #include #in..

이 문제를 요약하자면 1. 데이터를 받고 2. 자기보다 작은 숫자의 갯수를 출력한다. 라고 볼 수 있다. 즉, 이 문제를 풀기 위해서는 다음의 과정을 겪어야 한다. 1. 정렬을 한다. 2. 자기보다 작은 숫자의 갯수만 카운트 하되, 서로 다른 좌표의 갯수이므로 중복되는 것은 제거한다. 이때, 정렬하는 과정에서 O(nlogn)이고, erase까지 하는데 O(nlogn)가 사용된다. 추가로 자기보다 작은 숫자의 갯수를 전부 다 고려하려면 O(n^2)인데, 이 경우에는 시간 초과가 나므로 이분탐색을 활용해서 진행을 해주면 O(nlogn)이므로 충분히 2초안에 통과할 수 있음을 확인할 수 있다. 위의 방식을 활용하여 코드를 짜주면 다음과 같다. #include #include #include #include u..

가장 쉽게 생각할 수 있는 것은 브루트 포스이다.(전부 다 해보는 것) Brute force방법으로 하기 위해서는 숫자를 작은 것부터 계속해서 숫자를 키워나가면서 각 랜선을 해당 숫자로 나눈 몫의 합이 n보다 크거나 같으면 계속해서 숫자를 키워나가다가 n보다 작은 타이밍이 오면 그 직전까지의 숫자를 출력하는 방식으로 이해할 수 있다. 다만, 이 방식으로 진행하게 되면 시간초과가 나게 된다. 왜냐하면, 고려해야할 숫자의 범위가 maximum이 최대 랜선의 길이 x k(랜선의 숫자만큼 몫을 구해야하므로)가 된다. 이때 시간제한이 2초이므로 대략 10^8 * 2의 연산을 훨씬 초과한다. 즉, 단순히 연산하는 방식으로는 처리할 수 없음을 파악할 수 있다. 그 다음으로 생각할 수 있는 것은 이분탐색이다. 이분탐색..