Red Salmon

출처 : https://www.acmicpc.net/problem/1654

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/1654.cpp

처음에 이녀석을 어떻게 접근할지 고민하다가 결국 이진탐색이 아닌가 전부 다해보면 되겠다 생각했다. 하지만 실수가 있긴했다.

문제는 n만큼 혹은 그 이상만큼 토막을 내고 싶고 그때 하나의 길이가 가장 길게 하고 싶다는 것이다.

간단히 이진탐색으로 돌리면서 계산해보면 나올것 같지만 함정이 몇개 있다.

1. n과 꼭 떨어지지 않는 경우가 있다. 예를들어 인풋이
3 1200
1 1001 1002

이거라면 1을 하면 총 2천개 이상을 얻어 얻고자 하는 값인 1200보다 훨씬 큰 값을 얻을 수 있지만 2를 하면 1200개를 얻지 못한다. 그러므로 이때는 많이 버리더라도 1을 선택해야 한다.

2. 랜선의 길이가 2^31-1이라고 했다. 이는 인트의 거의 끝이라고 볼수 있는데 이진탐색에서 사용하는 mid는 2개의 수를 합한다음 나누므로 여기서 오버플루가 발생할 수 있다. 그러므로 long long을 써야 한다.

3. 처음  mid로 가능하지만 mid보다 더 큰 수일수도있다. 이진탐색을 하다보면 어느 미드값에서 만약 n을 구하면 종료를 할 수있다. 하지만 mid보다 더 큰 값이 올 수 있다.  이를 해결하기 위해서 n과 같은경우도 left를 갱신해 더 구해보도록 한다. 그리고 이과정을 무한히 반복하다가 left>right가 되는 순간 종료가 되는데 이때 right를 답으로 채택한다. 계속 반복하다보면 left는 계속 갱신이되고, mid는 옆으로 조금씩 가게 된다. 그리고 어느시점에서 불가능해질때 right를 출력하면 된다.

처음에 나는 단순히 k보다 n이 작은경우 k-n번째원소를 바로 출력하게 했는데 이게 참 문제였다. 생각해보면 인풋이
4 3
1 2 3 300

이라면 내 식대로의 계산에서는 1번원소가 출력이되지만 답은 100이기때문이다.

이런 함정만 피해간다면 답은 나올것이라고 본다. 

귀찮은 문제였다.

출처 : https://www.acmicpc.net/problem/10815

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/10815.cpp

이 문제의 경우 이진탐색 문제로써 그냥 오랜만에 풀어봤다. 뭐든 안하면 잊어버리는 법이기에 풀어보았다.

한번에 정답을 맞지 못했는데, M이 50만이면 입력도 50만 출력도 50만번을 해야 한다. 그런데 나는 cin cout을 사용하여 시간상 오버가 되었다. 과거에도 이런 경험이 많았기에, 바로 수정하였고 scanf와 printf를 사용하여 정답을 맞았다. 

다음주에는 조금 더 복잡한 이진탐색문제를 하나 풀어봐야겠다.