[백준 10160번] 암호 (Python3)

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. 패턴 2개는 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])

다음과 같이 나타낼 수도 있다.