Red Salmon

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

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/10827.java

이문제는 뭐 없다. 그냥 전부 계산하라는거다.

근데 이런건 자바가 최고다. C++로 하려면 구현해야할것들이 정~말 많다. 특히 곱셉의 경우 정~말 많다.

만약 코딩연습을 한다면 해볼만하지만...이미 다 알고..자바도 알고있기에 자바를 사용해서 풀었다.

다만 이번에 새로 안 함수가있다.

toPlainString()

나는 이 함수를 처음 사용해보았다. 아마 그전에도 써봤겠지만 기억을 못하고있다고 생각한다.

함수의 기능은 소수점 표기할때 중간에 자르지말고 전부 표기하라는 것이다. 

이것때문에 오답을 많이 맞다가 끝내 정답을 맞았다. 

할때마다 느끼지만... 걍 자바나 공부할걸 뭐한다고 C++을 공부해서 고생하는지 내 자신이 이해가 되지 않는다.

이번 하반기가 끝나고 취직하면 본업을 자바로 바꾸던지 해야겠다.