[백준] 2688_줄어들지 않아 (dp 이용)

📕 문제

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

2688번: 줄어들지 않아

 

💡 풀이법

: 우선 2자리수, 3자리수, 4자리수일때 경우의 수를 다 적어보면 규칙을 알 수 있다.

 

- 2자리수

끝자리수가 x 일때 나올수 있는 수

0 : 00

1 : 01 11

2 : 02 12 22

3 : 03 13 23 33

생략

 

- 3자리수

끝자리수가 x 일때 나올수 있는 수

0 : 000

1 : 001 011 111

2 : 002 012 112 022 122 222

3 : 003 013 113 023 123 223 033 133 233 333

 

위를 보면 3자리수에서 끝자리수가 1일때의 경우는 2자리수에서 끝자리수가 0일때와 1일때의 수에 1을 붙인 것과 같다. 3자리수에서 끝자리수가 2일때는 2자리수에서 끝자리수가 0일때, 1일때, 2일때의 수에 2를 붙인 것과 같다.

이 규칙을 점화식으로 적어보면 i가 자리수이고, j가 끝자리수일때

dp[i][j]= sum(dp[i-1][0]~dp[i-1][j]) 이다.

 

더 간단하게 쓰면

dp[i][j] = dp[i][j-1]+dp[i-1][j] 이 된다.

 

미리 dp라는 2차원 리스트에 64자리수까지 끝자리수에 따른 경우의 수를 다 구해놓고 N을 입력 받으면 바로 꺼내도록 구현했다.

 

T = int(input())
dp = [[1 for _ in range(10)] for _ in range(64)]

for i in range(1, 64):
    for j in range(1, 10):
        dp[i][j] = dp[i][j-1]+dp[i-1][j]

for _ in range(T):
    N = int(input())
    print(sum(dp[N-1]))