Red Salmon

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

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

이 문제는 자주 나오는 유형중의 하나이다. 쉬운문제에서 분할정복문제인데, 처음에 조금 고민을 했다.

만약 9개 파편을 쪼갰는데 그 나눠진파편과 옆 파편이 만나서 새로운 9개 영역을 만들면 어쩌나했는데

그런 복잡한 문제는 아니었다.

문제의 풀이는 다음과 같다.

1. chk함수를 만들어 x,y값과 크기를 입력하여 현재 일치하는지 체크를 한다.

2. 여기서 거짓이 되면 sz를 재설정하고 다시 검사를 한다.

3. 트루가 되면 그 부분을 건너띄고 다음 영역을 본다.

처음에는 크게보고 점차 줄여나가는 방식으로 진행하였다. 반대로 진행해도 되겠지만 이문제는 크게보고 작게접근하는게 맞는것 같다. 그리 어렵진 않은 문제였다.

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

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

과거에 분명 풀었던기억이 있는데 다른 문제인가보다. 

이문제 역시 공기와 노출되면 치즈가 녹아없어지는데 단순히 치즈에 구멍이 있는것은 공기에노출되지 않은것으로 간주한다.

또한 출력은 다없어지기전에 몇개였는지를 물어보고있다.

풀이를 생각해보면 입력이 최대 100이므로 100x100 이 검색이라고할때 하나씩 사라진다고해도 100x100x100이므로 n^3으로 충분히 풀 수 있는 시간이다. 

그래서 나는 매번 스캔을 하면서 공기와접촉한 치즈영역을 찾고 해당영역을 지우는식으로 풀었다. 그리고 시간내에 간단히 풀렸다.

큐를 두개를 두어 풀었는데 이런 손이 많이가는 문제가 시험문제내기 좋은 문제라고생각한다.

왜냐면 계산 실수나 작은 손실수가 답을 해매게 만들기 때문이다.

많은 연습만이 이런실수를 줄일수있다.

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

        https://www.acmicpc.net/problem/11726

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

        https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/11726.cpp

둘다 DP문제로 어려운 DP가아닌 기초 DP이다. 그냥 숫자놀이에 불과하다. 타일링 문제는 전에 3xn타일링 풀때보다 훨씬 쉬웠고, 동물원은

테스트케이스만들기가 조금 귀찮았었다. 

근데 뭐 너무도 흔한 DP여서 금방풀었다.

이제 이런  DP는 아주 쉽게 풀 수 있게 되었다.

출처 : 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이기때문이다.

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

귀찮은 문제였다.