Red Salmon

출처 : 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분정도면 푸는 문제가 되었다. 

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

출처 : 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배를 하면 바로 전전수를 빼주면 값이 나온다는 가설이 세워졌고 도전해봤다.

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