[백준] 2193번, 이친수 (Python)

문제

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

2193번: 이친수

 

코드

n = int(input())
dp = [0 for _ in range(90)]
dp[0] = 1
dp[1] = 1
dp[2] = 2
for i in range(3, n):
    for j in range(i-1): # i자릿수 - 2 까지 전부 더하고 +1
        dp[i] += dp[j]
    dp[i] += 1
print(dp[n-1])

n = 6 일때
1 0 0 0 0 0 - 6
1 0 0 0 0 1 - 1
1 0 0 0 1 0 - 2
1 0 0 1 0 0 - 3
1 0 0 1 0 1 - 3
1 0 1 0 0 0 - 4
1 0 1 0 1 0 - 4
1 0 1 0 0 1 - 4

4자릿수 + 3자릿수 + 2자릿수 + 1자릿수 + 1

구하고자 하는 자릿수 - 2 까지 전부 더하고 새로운 자릿수 + 1 해주면 된다.