ACM 10069, Distinct Subsequences

동적 프로그래밍 기법을 익히고자, 관련 문제를 풀고 있다. 이번은 결과가 10의 100승까지 나온다는 점을 잊은데다, string으로 변환하고 다시 정수로 변환하는 등의 거추장스런 짓을 했더니 time limit도 나오고 해서, 프로그램을 두번이나 엎었다... 한심하다.

 

 

문자열과 단어를 입력받는다. 문자열 안에 단어의 조합이 몇 번 나올 수 있는지 체크한다. 순서는 유지되어야 한다.

 

http://acm.uva.es/p/v100/10069.html

 

 

[풀이]

 

동전 문제의 응용이다.

 

예를 들어 aaabbb 문자열에서 abb의 조합을 찾아보자.

일단 ab가 aaabb에서 나오는 회수를 x라 하자. 그리고 단어 b의 회수는 1이다(abb는 반드시 ab가 나오면 끝에 b가 나와야 올바른 조합이 되므로 1이다). 따라서 abb의 조합 회수는 x * 1 = x 이다.

 

그럼 그럼 a가 aaab에서 나오는 회수가 y라 하자. 그러면 ab의 확률은 얼마나 될까? b가 반드시 조합이 되어야 a의 회수가 유의미하므로, ab의 조합 회수는 y가 된다.

 

그러므로 abb의 조합 회수를 구하려면, b를 제외한 ab의 조합 회수가 필요하다. 이의 이유는 위에 설명했다. 그리고 이전까지 구한 조합이 일단 필요하다. 새로운 글자가 나오면 조합은 이전과 별개가 되기 때문이다.

 

따라서 식은 다음과 같이 도출된다.

 

조합 회수 = 이전 결과 + 끝 문자를 제외한 단어의 조합 회수

Distinct Subsequences.cpp

Distinct Subsequences.exe

input.txt