저는 조합론으로 풀었죠 핳하

중복순열과 중복조합!

전 백트래킹해서 다 구하고 제출할려했는데 50%task가 10^300초...걸리더라고요 ㅎ

힌트를 드리자면

n 개의 문자를 사용해서 나올 수 있는 암호의 갯수는 2가지가 있습니다.

첫째, 앞의 n-1 개의 문자가 이미 암호문일 때

둘째, 앞의 n-5 개의 문자가 암호문이 아니고 추가될 5개의 문자가 암호문이 될 때

이 때 앞의 암호문이 아닌 문자열의 끝부분의 2개의 문자가 AB 일 때, ABCBC 가 추가되면 첫째와 둘째에서 두 번 세어지게 됩니다.

따라서 이 경우를 빼주면 총 암호문의 개수가 나옵니다만.. 저도 이게 정확한지는 모르겠습니다.

부디 해결하시길 바랍니다 ㅎㅎ

"D[i, status] = i번째 문자열까지 고려할 때, 상태가 status일 때 ABCBC와 ABABC가 들어가있지 않은 문자열의 갯수"로 정의하여 접근할 수 있어요. O(N*상수)에 풀 수 있는데 오토마타 개념을 사용하여 시간을 더 줄일 수 있겠네요.

조합론으로는 어떻게 풀 수 있는지 궁금하군요

오늘 공홈에 풀이와 문제가 올라왔네요

문제 올라오면 한번 풀어봐야겠습니다

답글 달아주신분들 감사해요

조합론으로 하면 중복순열과 제 2 스털링 수를 통해 풀 수 있죠ㅎㅎ

근데 몇일전에 깨달았는데 쓰라는 스털링은 안쓰고 중복조합 때려넣음ㅋㅋㅋㅋㅋㅋㅋㅋ

이해가 잘 안되서 그런데 중복순열과 제 2 스털링 수로 겹치는 부분을 어떻게 카운트해주죠?

음.. 중등부 4번 문제네요..

할 수 없이 1, 2, 3만 정확히 풀고 나왔죠.. ㅠㅠ