Red Salmon

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/9466.cpp

이 문제는 단순히 사이클을 찾고 끝내는 문제라고 생각했다. 그러나 학생이 무려 10만명이기 때문에 이중포문만 돌려도 TL을 피할 수 없다.

그래서 한번에 하는 방법을 생각해봤는데 O(n)은 사실상 불가능하고 내생각엔 O(2n)정도가 최대일것 같다. 

방법은 다음과 같다.

1번학생부터 n번학생까지 포문을 돌리되 1번학생과 연관된 모든 학생을 체크하면서 지워나간다. 이때 써클이 되는지 안되는지는 번호를 부여함으로써 알 수 있다. 써클이 되면 사용된 학생을 다시 돌아오게되고 이때 이 학생 직전에 몇번을 부여했는지를 파악하면 된다. 써클이 되지 않는 경우는 존재하지 않는다. 반드시 어디선가는 끝나야하기 때문이다. 

위와 같은 방법을 사용하면 빠르게 끝낼 수 있다.

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/2186.cpp

이 문제는 과거 오답을 맞았다가 다시 도전해서 정답을 맞은 문제이다.

이 문제도 뭐 별거 없어보이지만 최대 움직이는 칸이 정해져있어 그 안에서 자유롭게 이동이 가능하다.

즉 일반적인 DFS로는 풀 수 없다. 왜냐면 사용한 녀석을 다음 녀석이 또 사용할 수 있기 때문이다.

그래서 생각한게 3차원배열과 DP이다. 

먼저 배열의 입력을 받고 dp배열을 3차원으로 만든다.

2차원은 그냥 입력과 동일한녀석이고 3차원이 되면서 글자의 개수를 의미하게 된다.

그리고 하나의 점마다 모두 계산해본다. 

dp+dfs에서는 패턴이 정해져있다. 해당 녀석이 존재하면 리턴하고 존재하지않으면 갱신하는 방식이다.

나는 각 점을 검사하면서 글자수를 할당시켰고 최종적으로 갱신 후 리턴하는 방식을 사용했다. 

이와 비슷한 문제로 1005번? ACM craft(위상정렬)와 이분매칭알고리즘이 있다.

간혹 햇갈리는 부분이 있다면 dp가 존재할때 새로이 갱신할때가 있는데 이는 dp가 존재한다고 리턴할때가 아니라, dp를 토대로 새로운 경우를 조사할때이다. 근데 이것은 그런경우가 아니라, 그냥 해당 구간에 몇개가 조사되었는지 알아내고 그걸 다시 사용하기만 하면 되는 경우이다. 

즉, 최대값을 구하는것인지 아니면 가짓수를 갱신하는지 여기에 초점을 맞추면 된다.

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

정답 :  https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1339.cpp

이 문제 역시 DFS 문제이다. 

걍 다 때려보면 된다. 집중해야할 것은 알파벳의 최대가 10개뿐이며 최대길이는 8개이다. 또한 10줄까지 입력이 들어온다.

방법은 다음과 같다.

입력된 알파벳을 전부 모은다. 그리고 그 알파벳에 9부터 시작해서 점차 하나씩 줄여가는 방식으로 수를 매긴다.

계산을 전부해보고 다시 알파벳의 순서를 바꿔 9부터 대입한다.

물론 다른 방법도 있다. 알파벳의 순서를 유지한채 숫자만 계속 바꾸는 식이다. 결국 똑같은 방법이다.

그런데 내가 가진 의문점은 내가 작성한 소스는 특정 경우에서 TL을 피할 수 없다. 그런데 문제에서는 정답을 준다.

그래서 정답자의 소스들을 토대로 계산해봤는데 대다수의 정답자들이 TL이 나왔다. 

이문제의 최적의 해결법을 찾기 위해 우수정답자의 소스를 보니 수로 변환후 바로 연산하는 방식인것 같다.

아 그리고 하나더 말하자면 dFS를 직접짜는것보다 STL의 next_permutation을 사용하는게 속도면에서 빠르다.

아무렴 STL이기 때문인것 같다. 내부 구조가 저번에도 말했듯이 재귀가 아니라 반복문이라는게 참 신기하다.

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/3109.cpp

이 문제는 얼핏봐서는 정말 어려운 문제였다. BFS로 하자니 딱히 최적의 답이 떠오르지 않았고, DFS로 하자니 시간이 오래 걸릴 것 같았다.  정말 방법을 찾지 못했다.

그러다가 정답자의 소스를 보고 이게 된다고? 생각을 하며 곰곰히 되집어보니 가능하리란 생각이 들었다.

키워드는 다음과 같다. 길은 정해져있으며 어떤녀석이 그 길을 가면 두번다시 못간다.

길이 있다면 누가 시작하더라도 반드시 갈 수 있다. 어떻게 막 움직이더라도 가능하다는 말이다. 

이것에만 집중하면 코드가 보인다. 

그래서 DFS로 풀었다. 참 좋은 문제라고 생각한다.