algospot 보안종결자(문제 ID: NH) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/NH

algospot.com :: NH

입력으로 주어지는 특정한 문자열 패턴들이 나타나지 않게 알파벳 소문자로만 이뤄진 n자리 암호를 만들 수 있는 모든 경우의 수를 10007로 나눈 나머지를 구하는 문제이다.

bruteforce로 풀게되면 26^n의 시간복잡도를 가지게 되므로 제한시간 안에 문제를 푸는것이 불가하다.

동적계획법을 이용하면 문제를 풀 수 있는데 그 방법이 매우 어렵고 까다롭다. (종만북의 연습문제중 가장 어려웠던것 같다.) 

먼저 입력으로 주어진 문자열 패턴들을 트라이로 만들고 각 노드마다 상태를 부여한다.

앞으로 만들어야하는 글자의 갯수 length, 현재 트라이의 상태를 state라 했을때 cache[length][state]형태의 캐시를 이용한다.

하지만 이렇게 트라이를 이용한 동적계획법을 구현하기 위해서는

먼저 트라이의 각 노드들이 실패연결과 출력문자열을 가지고 있어야하고, 각 노드마다 상태 번호가 부여되야 한다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/26.%20Trie/nh.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2