백준 10844번 동적계획법 -python

얕은 복사와 깊은 복사 개념으로 import copy를 이용하여 해결할 수 있는 문제가 있어 들고 왔다.

단계별 풀어보기 동적계획법1에서 가장 낮은 정답 비율을 기록하고 있는 문제이다.

 

 

문제

---

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

 

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

 

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

 

문제가 정말 짧게 설명되어있는데 짧다고 쉬운 것이 아니다.

 

 

 

풀이

---

먼저 계단 수를 알아야 하는데 앞 뒤의 인접한 수가 자신보다 1 작거나 1 크거나 하는 수이다.

EX) 132, 10234

 

입력에서의 N은 계단 수의 자릿수를 나타낸다.

 

만약 N = 2 일 경우는 두 자리 수의 계단 수인

10, 12, 21 .... 89, 98 총 17개가 나온다.

 

동적계획법(dp) 문제임으로 접근 방법에서 미리 저장된 데이터를 활용하는 방법을 생각해야 한다.

 

먼저 N이 1인 경우를 생각해보면

1 2 3 4 5 6 7 8 9  총 9가지가 나오고

 

N 이 2인 경우를 살펴보면

N = 1인 전 데이터에서 각 숫자의 +1, -1이 숫자가 붙게 된다.

 

하지만 끝자리가 0이거나  9인 경우는 01, 98처럼 한 숫자가 고정으로 들어가게 된다.

 

따라서 점화식을 생각해보면

 

$$ f(x) = (f(x - 1) - (0, 9))  *  2  -  (0, 9) $$

 

즉 끝자리가 0 또는 9인 경우를 제외한 경우에 2를 곱하고

제외한 0, 9의 경우를 더하면 다음 수가 나오게 된다.

 

그럼 코드를 짤 때 마지막 숫자가 0이거나 9인 경우와 1 ~ 8인 경우 를 나누어 주면 된다.

 

 

코드

---

여러 가지 방법이 있겠지만 나는 모든 경우의 수를 배열로 만드는 것이 아닌 

 

0 ~ 9의 수가 몇 번 나오는지만 알아내어

 

0 ~ 9의 숫자가 나오는 횟수의 총합이 경우의 수가 된다는 것을 이용할 것이다.

 

 

횟수를 알아내는 방법은 

 

0과 9는 1과 8의 갯수와 같고,

 

1에서 8은 양 옆의 갯수(ex 2일 경우 1과 3의 횟수의 합)의 합과 같다.

 

즉 f(x - 1)의 횟수만 저장해놓으면 f(x)의 횟수를 구할 수 있다.

 

n = int(input())

dp = [0] * 10 # f(x) 저장 배열
dpnum = [0] * 10 # f(x - 1) 저장 배열

for s in range(1, 10): # N = 1인 경우 1 ~ 9 모두 1번이다.
  dp[s] = 1
  dpnum[s] = 1

 

이제 이중반복문을 이용하여 f(x)를 구하면 된다.

 

for k in range(n - 1):
  for i in range(0, 10):
    if i == 0: # 0인 경우
      dp[i] = dpnum[i + 1]
    elif i == 9: # 9인 경우
      dp[i] = dpnum[i - 1] 
    else: # 1 ~ 8까지인 경우
      dp[i] = dpnum[i - 1] + dpnum[i + 1]

 

안쪽 반복문을 다 돌았을 경우 

dpnum 값에 dp 값을 넣어줘야 한다.

 

여기서 깊은 복사를 사용하여야 한다.

dpnum = dp 를 할 경우에 dp와 dpnum은 같은 배열이 된다.

 

python의 copy를 사용하여 깊은 복사를 해주면 된다.

 

import copy

 

dpnum = copy.deepcopy(dp)

 

최종 코드

---

import copy # deepcopy() 를 사용하기 위한 copy import

n = int(input())

dp = [0] * 10
dpnum = [0] * 10

for s in range(1, 10): # N = 1 경우 설정 1~9까지 1번
  dp[s] = 1
  dpnum[s] = 1
  
for k in range(n - 1):
  for i in range(0, 10):
    if i == 0: # 0인 경우
      dp[i] = dpnum[i + 1]
    elif i == 9: # 9인 경우
      dp[i] = dpnum[i - 1] 
    else: # 1 ~ 8경우
      dp[i] = dpnum[i - 1] + dpnum[i + 1]
  dpnum = copy.deepcopy(dp) # 깊은 복사를 이용
  
result = 0
if n == 1: # N = 1인 경우는 바로 9를 출력
  print(9)
else:
  for j in range(0, 10):
    result += dp[j]
  print(result % 1000000000)