출처 : 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이기 때문인것 같다. 내부 구조가 저번에도 말했듯이 재귀가 아니라 반복문이라는게 참 신기하다.


'Algorithm' 카테고리의 다른 글

[AC] 9466 텀 프로젝트  (0) 2016.08.18
[AC] 2186 문자판  (1) 2016.08.18
[AC] 1339 단어수학  (0) 2016.08.18
[AC] 3109 빵집  (0) 2016.08.18
[AC] 10827 a^b  (0) 2016.08.18
[AC] 11057 오르막 수  (0) 2016.08.03

+ Recent posts