Red Salmon

출처 : https://algospot.com/judge/problem/read/BOARDCOVER#

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/AOJ%20boardcover.cpp

이 문제도 약 1년만에 드디어 풀었다. 

풀고나서 생각해보니 1년전에도 거의 다 풀었었는데 마지막 실마리를 찾지 못했던 것이었다. 

3점이 있는 도형을 어디를 기준으로해서 만들것인지인데 탐색을 왼쪽에서 오른쪽으로가고 위에서 아래로 가기때문에 거기에 초점을 맞추고 구현을 해야 하는데, 자꾸 다른 모습으로 하다보니 정답이 나오지 않았던 것이었다.

하... 지금이라도 알아서 참 다행인 실수이다. 

결코 어렵지 않았으나, 내가 간과한 실수가 문제였다.

출처 : 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로 풀었다. 참 좋은 문제라고 생각한다.