jng6017   1년 전

D[i]=길이가 i까지 일떄 안전한 비밀번호 수

안전 하지 않은거는

D[i-5]에서 ABABC

D[i-5]에서 ABCBC 2개 붙는거라서

D[i]=D[i-1]*k - D[i-5]*2


위의 다이나믹이 틀린 이유를 찾을려는데 찾지 못하겟습니다 ㅠ 도와주세요..

pichulia   1년 전

ABABCBC

이 문자를 생각해봅시다.


D[i-1]*k 로 계산된 비밀번호들의 집합에는

ABABCBC 가 포함되어있지 않을겁니다.

왜냐하면 ABABC <-- 이부분이 D[5]에서 제외되었기 때문이죠...


하지만 지금 D[i-5]*2 에서 AB + (ABCBC) 이 비밀번호를 빼려고 하고있습니다.

즉, D[i-1]*k 로 구성된 비밀번호들의 집합에 "없는" 문자를 뺐기 때문에

실제로 가능한 비밀번호보다 더 작게 계싼되게 됩니다.


실제로 7 3의 경우 2134 가 정답이지만

위의 다이나믹으로는 2133이 나오게 됩니다.

딱 ABABCBC 를 더 빼버린 만큼의 숫자가 나오죠...

pichulia   1년 전

덕분에 숏코딩 상위권이 됐습니다. 풀이 공유해주셔서 감사합니다.

jng6017   1년 전

도와주셔서 감사합니다

댓글을 작성하려면 로그인해야 합니다.