[BOJ][Python]2193 풀이

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

2193번: 이친수

n = int(input())
t = [0 for _ in range(91)]
t[1] = 1
for i in range(2, 91):
    t[i] = 1 + sum(t[:i-1])
print(t[n])

뻔한 dp 문제입니다. 조건 1과 2에 의해서 앞의 두 자리는 10으로 고정되기 때문에 사실상 3번째부터 n번째 까지 가능한 조합을 따지는 건데 그 조합들은 이미 앞에서 구한게 있으니 그대로 사용하시면 됩니다. 조금 더 머리를 쓰면 sum 메서드를 사용하지 않고 코드를 작성해서 시간복잡도를 더 줄일 수 있겠죠.