Problem Solving/BOJ
[BOJ][Python]2193 풀이
NoiB
2023. 3. 3. 20:00
반응형
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
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 메서드를 사용하지 않고 코드를 작성해서 시간복잡도를 더 줄일 수 있겠죠.
반응형