Red Salmon

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

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

이 문제는 딱봐도 DP이다. 그런데 정말 귀찮았다. DP 수식을 만들려면 기본적으로 n이 한 4정도까지는 테스트샘플이 필요한데 

이녀석은 수작업으로하기에 너무나도 많았다. 정말 급증하는 수준이었다.

문제를 보면 홀수일때는 생각할 필요도없이 0이다. 왜냐면 2*1타일로 3*3, 3*5 이런타일은 채울 방법이 없다는것은 누구나 알기 때문이다.

그래서 짝수만 보면 되는데 문제는 예제로 2일때 3이라고 알려줬다. 그래서 나는 4일때 수작업으로 해보니 11이 나왔다.

하지만 3 11 로는 어떠한 수식도 짐작하기 힘들다. 그래서 6일때 얼마인지 구해보기로 했다. 

수작업으로 그려보니 약 10분정도 걸렸고 41이라는걸 알았다.

3 11 41이 나오니 수식이 감이 왔다. 현재 i값에 3배 혹은 4배를 한후 어떤 처리를 했다는 의미인것 같았고, 3배를 할때와 4배를 할때 얼마나 차이있나 봤더니, 4배를 하면 바로 전전수를 빼주면 값이 나온다는 가설이 세워졌고 도전해봤다.

그게 정답이었고, 문제푸는시간보다 손으로 그리는 시간이 훨씬 길었던 문제이다.

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

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

이문제는 네트워크유량 문제이다. 즉 이분매칭이다. 

요즘 나는 이분매칭에 흠뻑 취해있다고 해도 과언이 아닐것이다. 그도 그럴게 하도 많이 틀려서 빡쳤다..결국 DFS인데..

암튼 이문제는 저번에 푼 축사배정문제와 완전히 똑같다고할수있다. 결국 최대매칭을 구하는 문제인데 소스마저 똑같다.

인풋이 똑같기 때문이다. 그냥 코딩연습이라 생각하고 풀었다.

문제는 어렵지 않다.

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

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

이 문제는 간단한 BFS문제이나 나는 정말 정답을 맞지 못했다. 결국 맞긴했지만 어처구니없이 맞지 못하였기에 적는다. 

우선 문제는 x-1, x+1, x*2 이 3가지에 대해서 bfs를 돌리면 된다. 그런데 내가 놓친 부분은 중복을 계산하지 않았고 결국 메모리문제에 걸리게 되었다.

나중에 따로 중복체크하는 배열을 만들어서 확인을 하게 하였고 그후 정답을 맞았지만 어처구니없었다.

BFS에서 가장 중요한것은 중복체크인데 이 부분을 간과 하고있었다.

쉬운 알고리즘이기에 한동안 안했더니 바로 이런 실수를 하였다. 앞으로 간간히 해야겠다. 

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

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

이 문제는 이진탐색 문제이다. 문제를 딱보니 DP아니면 이진탐색의 느낌이 강했고, 더 살펴보니 이진탐색 문제였다.

DP 문제가 아니라는건 뭔가 감이었다. 예전에는 이런 구분이 잘 안되었는데 이젠 그냥 뭔가 보인다.

 문제는 어떤 기점으로 잘랐을때 요구한 길이에 가장 근접하게 자르라는 말이다.  예전에 황소 울타리문제? 그거랑 비슷한거 같다.

접근은 다음과 같다.

1. 정렬한다.

2. 먼저 입력값을 통해 대강적인 위치를 찾는다. (지금 생각해보니 굳이 찾을 필요가 없다.) 대강적인 위치는 입력배열의 인덱스이다.

3. 해당 인덱스를 통해 left right값을 구하면 이제 값은 arr[left]<=정답<=arr[right] 인것이기 때문에 범위가 상당히 좁아졌다. 여기서부터는 인덱스가 아닌 값으로써 다시 검색을 한다.

4. 일치되는 값이 있으면 그 값을 리턴하고 없다면 middle을 가지고 다시 state함수를 호출하여 middle을 그대로 사용할지 아니면 -1을 해줘야할지 판별한다. 

이 문제를 풀면서 조금 졸렸고, 코드가 길어져 짜증나 계속 줄이려고했는데 생각해보니 몇몇의 개선점이 보인다.

1. state함수는 계속 합을 구하는 함수인데, 좀 더 생각해보면 처음 이진탐색이후 3번과정을 할때는 이미 arr[right]로 값이 변경된 시점에서 right는 고정이 되었으므로 한번에 합을 구하고 그 후부터는 인덱스가 변할때 그 차만큼 +1 혹은 -1을 해주면 되지 않았을까 싶다. 그러면 굳이 처음부터 끝까지 합을 구하는 과정이 많이 생략되었을거 같다. 뭐 어차피 로그시간대라서 그냥 무시하고 진행하였다...

2. 나는 이진탐색을 둘로 나누었는데 지금 생각하니 굳이 그럴 필요가 없는것 같다. 하나만두고 처음부터 값을 통해 찾았다면 더 나은 코드가 되지 않았을까 생각이 든다. 역시 졸릴땐 문제를 풀면 안되는것 같다. 코드가 더 간략해지고 깔끔해질수있었을텐데 하는 아쉬움이 남는다.