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/1620

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

문자열 + 이진탐색 문제이다. 어려울건 없었다. 그냥 따로 분리를 하여 숫자용 하나 문자용 하나 두고 검색하여 정답을 출력하면 된다. 딱히 고민했던 에러사항도 없다.

다만 입력이 10만번에 출력도 그만큼이다. 즉 cin은 안되는데 대충보고 그냥 했다가 시간초과가 났다.

이 부분만 고쳐주면 된다. 

그리고 string형식은 그냥 <, > 으로 비교가 가능하지만  char * 형식은 저런 비교가 되지 않으니 반드시 strcmp를 써야 한다. 물론 string형식도 compare함수가 존재하지만 <, >로도 원하는 결과를 얻을수 있다.

마찬가지로 string은 =로 값을 대입할수있으나 char * 는 불가하므로  strcpy를 사용해야 한다.

참으로 C++은 편리한 것이다.  또한 이런정도 함수들은 알고 있어야 문제풀기 수월할 것이다.

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

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

이 문제는 나를 참 힘들게하였고 덕분에 이분매칭에 대해 공부하게된 계기를 준 문제이다. 문제자체는 별거아닌것 같지만 참 별거인문제이다.

5달전 처음으로 도전하여 실패하였고 최근 3주간 매주 도전하여 결국 풀어냈다.

처음 이문제을 단순 DFS로 도전하여 실패하고 한 유저분이 이분매칭을 사용하라고해서 공부를 했다.

그리고 이문제에 대한 다양한 접근법을 생각해봤다.

결국 소수가 되기위해서는 홀수+짝수인 경우만 가능하기에 (홀수+홀수, 짝수+짝수는 결국 짝수가 되고 이는 절대 소수가 아니다.) 두개의 입력을 분리하여 보관하고 하나씩 매칭하는 방법을 하려했다. 그런데 아무리 생각해도 이렇게 하니 일이 복잡해지는 느낌이었다.

더 간단히 더 기본에 충실한 알고리즘을 생각하다가 저번에 푼 이분그래프 문제가 생각이 났다. 그 문제역시 입력을 복제하여 두개의 그룹처럼 생각하고 접근하였는데 그 방법을 여기서 도입해도 될거라 생각했다.

그래서 이런 로직을 세웠다.

1. 먼저 소수확인용 배열을 만들고 함수로 배열을 완성한다.

2. int형의 일반 배열에 인풋을 담아둔다.

3. 2번에서 받은 배열로 각 위치의 숫자당 소수가 이루어질수있는 녀석을 푸시하여 2차원 벡터를 만든다. 여기서 그래프로 만들기위해 반대선을 만들지 않는 이유는 결국 나는 하나의 입력을 가지고 전부 돌기 때문에 굳이 하지 않아도 반대선이 체크가 되기 때문이다.

3. 과거 수차례 작성했던  bpm함수를 만든다. 하지만 여기서 중요한것은 첫번째수와 매칭되는 수는 제외하고 생각해야 한다는 점이다. 그래서 38, 39번라인으로 bmatch를 값을 주고, 45번줄에 이미 사용함을 체크한다. 그리고 dfs함수는 과거 작성했던 이분매칭소스와 완벽히 동일하다.

4. 이 함수에서 매칭값이 n-2가 나오면 모든 수에 대해 매칭이 완전히 이루어진다는 말이므로 이 값을 ans에 푸시한다. 보통은 매칭값이 한쌍이냐 아니냐로 따지지만 이문제에서 나는 하나의 인풋을 두개의 그룹으로 나누어 생각하였기 때문에 각 수마다 전부 매칭이 루어지는지 체크해야만 한다.

5. ans가 비어있으면 -1 아니라면 sort를 해준다.

이렇게하니 소스도 그렇게 길지 않았고, 로직도 간단히 하여 풀렸다. 특별한 기술도 들어가지 않고, 그냥 기본에 충실한 이분매칭법으로 풀수있었다. 풀다보니 과거 DFS처음 공부할때 풀었던 Prime Ring Problem문제가 생각났다. 아마 나는 이문제를 잊지 않을것 같다.

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

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

이 문제역시 DP이다. 근데 참 친절하게 예제가 많다.  그리고 이런 문제는 전형적인 DP유형중의 하나이다. 과거 동전문제를 풀었었는데 그것과 설명만 다를뿐 똑같은 문제이다. 

결국 i일때부터 하나씩 처리하면 되는 문제이다. 뭐 생각도 별로 안한 DP문제인데, 불과 1년전에는 이런문제 풀지도 못했는데 이제는 5분에서 10분정도면 푸는 문제가 되었다. 

역시 알고리즘은 꾸준히 하는게 중요한거 같다.