(백준 10160호) 암호(Python3)

by 

N,K = map(int,input().split())
DP = (1)*(N+1)
for n in range(1,N+1):
  DP(n) = DP(n-1)*K
  if n>4:
    DP(n) -= DP(n-5)*2
  if n>6:
    DP(n) += DP(n-7)
  DP(n) %= 10**9+9
print(DP(N))

DP에서 해결했습니다.

해결책을 설명하자면,

1. 길이가 n일 때 비밀번호 케이스의 수를 나타내는 DP 배열을 생성합니다.

2. 패턴을 고려하지 않는 경우 DP(n) = DP(n-1)*K. (한 글자 추가)

'추천 관련글,

3. 이때 패턴이 없어야 하므로 DP(n)에서 DP(n-5)*2를 뺍니다. (패턴의 길이가 5이므로)

4. 두 패턴은 ABCBC와 ABABC이며, 이 두 패턴은 ABABCBC와 겹칠 수 있으며, 겹친 경우는 이 경우뿐입니다. 따라서 포함-배제 원칙에 따라 DP(n)에 DP(n-7)을 더한다.

5. 출력 DP(N).

재귀 수식만 찾으면 구현이 간단합니다. 위의 코드를 약간 단순화

N,K = map(int,input().split())
DP = (1)+(0)*N
for n in range(N):
  DP(n+1) = (DP(n)*K-DP(n-4)*2+DP(n-6))%(10**9+9)
print(DP(N))

다음과 같이 표현할 수도 있습니다.