[Python] 백준 14437번: 준오는 심술쟁이!!

https://www.acmicpc.net/problem/14437

14437번: 준오는 심술쟁이!!

 

 > 접근

위 테이블로부터 DP[문자열 인덱스][지금까지의 변경 횟수]를 정의할 수 있다. 만약 변경 횟수가 각각 [0,1,1,0,0]이라면 다음과 같은 순서를 따른다.

 

또 고려해야 할 사항이 있는데, 바로 1 <= k <= 25로 제한되어 있는 변경 범위이다. 입력이 다음과 같다고 해보자.

 

28
hanjo

 

처음에 h에서 1번 했다고 했을 때, 이것이 다음 DP에 영향을 주는 범위는 a에서 [1, 26]이다. 왜냐하면 a에서 0~25번을 변경할 수 있기 때문이다. 이에 따라 다음과 같은 식이 성립한다.

 

DP[i][k] = sum(DP[i-1][k-25:k+1])

 

이것을 바탕으로 코드를 작성했을 때, 부분합의 이용하여 최적화를 시킬 수 있었다. 무식하게 [k-25, k] 범위를 더하는 것이 아니라 부분합을 이용하여 더욱 효율적으로 결과를 계산할 수가 있다.

 

또한 DP가 바로 직전(DP[i-1])의 데이터만을 참조하므로 1차원 배열로 두고 풀 수가 있다.

 

# -*- coding: utf-8 -*-
import sys                           
input = sys.stdin.readline       
INF = 1000000007
                           
if __name__ == '__main__':
  s = int(input())            
  n = len(str(input().rstrip()))      
                               
  dp = [0]*(s+1) # dp[k]: k만큼 바꿨을 때의 경우의 수
  dp[0] = 1
  next_dp = [0]*(s+1)

  for _ in range(n):                      
    prefix_sum = 0

    for k in range(s+1):     
      prefix_sum = (prefix_sum + dp[k]) % INF
      if k > 25: # 1 <= k <= 25(문제 조건)이므로 부분합의 범위를 조절해줌
        prefix_sum = (prefix_sum - dp[k-26] + INF) % INF

      next_dp[k] = prefix_sum

    # dp에 next_dp값을 가리키게 하기 위해 포인터를 스왑해준다.
    # 어차피 next_dp는 초기값에 상관없이 갱신되므로 dp를 가져도 상관 없다.
    dp, next_dp = next_dp, dp

  print(dp[-1])