Red Salmon

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

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

솔직히 매우 쉬운문제이다. 다만 처음에는 틀렸었는데 만약 인풋이

5 1

2

일때 나는 1을 제거하면 2번과 3번을 실행하지 않으니 0이라고 생각했다. 

하지만 제거하는건 반드시 일치하여야만 할때였다. 그래서 그부분만 다시 처리해줬고 정답을 받았다.

이 문제는 deque를 알면 쉽지만 만약 몰랐다면 구현에 상당히 애먹었을것 같다. 

출처 : 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는 아주 쉽게 풀 수 있게 되었다.