반응형
<코드>
#include<iostream>
#include<algorithm>
using namespace std;
long long n, dp[1001];
int main()
{
dp[1] = 1;
dp[2] = 1;
dp[3] = 2;
cin >> n;
for (int i = 3; i <= n; i++)
{
dp[i] = 1; // 1000....0 과 같은 경우의 수
for (int j = 1; j <= i - 2; j++)
{
dp[i] += dp[j];
}
}
cout << dp[n];
}
풀이 방법
4자리 수
- 1000
- 1001
- 1010
dp[4] = 1 + dp[1] + dp[2]
5자리 수
- 10000
- 10001
- 10010
- 10100
- 10101
dp[5] = 1 + dp[1] + dp[2] + dp[3]
6자리 수
- 100000
- 100001
- 100010
- 100100
- 100101
- 101000
- 101001
- 101010
dp[6] = 1 + dp[1] + dp[2] + dp[3] + dp[4]
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
반응형
'🧩PS > 🥈Nomal' 카테고리의 다른 글
| [C/C++] 백준 10845번 - 큐 (0) | 2021.02.06 |
|---|---|
| [C/C++] 백준 9095번 - 1, 2, 3 더하기 (DP) (0) | 2021.02.06 |
| [C/C++] 백준 11726번 - 2×n 타일링 (DP) (0) | 2021.02.06 |
| [C/C++] 백준 4386번 - 별자리 만들기 (MST, 크루스칼) (0) | 2021.02.05 |
| [C/C++] 백준 15988번 - 1, 2, 3 더하기 3 (0) | 2021.02.04 |