티스토리 뷰
728x90
반응형
문제
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
코드
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 해주면 된다.
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 10451번, 순열 사이클 (Python) (0) | 2021.08.08 |
|---|---|
| [백준] 1389번, 케빈 베이컨의 6단계 법칙 (Python) (0) | 2021.08.07 |
| [백준] 1912번, 연속합 (Python) (0) | 2021.07.30 |
| [백준] 10815번, 숫자 카드 (Python) (0) | 2021.07.27 |
| [백준] 1162번, 도로포장 (Python) (0) | 2021.07.22 |
댓글