2201번: 이친수 찾기
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 들 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
dp[length] : 길이가 length인 이친수의 시작 번호
1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11은 이친수가 아니다.
위 조건을 고려하여 길이당 이친수의 갯수는 피보나치 수열로 구할 수 있습니다.
저는 이를 이용하여 dp에 각 길이당 시작하는 번호를 담아놓습니다.
dp[1] = 1, dp[2] = 2, dp[3]= 3, dp[4] = 5, dp[5]=8, dp[6] = 13, ... 이런식으로 되고,
그리고 입력받은 N의 길이를 구합니다.
길이가 i일 때의 시작번호와 비교를 하여 dp[i] > N이면 length는 i - 1입니다.
그리고 length만큼 반복문을 돌려주면서 두 가지의 경우를 확인합니다.
1. dp[length] <= N이면 (번호 N이 length의 시작점보다 뒤에 있으면)
=> 1을 출력하고 N을 N의 시작번호만큼 빼줍니다.
2. dp[length] > N이면 (번호 N이 length의 시작점보다 앞에 있으면)
=> 0을 출력합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <iostream>
using namespace std;
typedef long long ll;
ll dp[91], N;
void init() {
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= 90; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
}
void solve() {
int length = 0;
for (int i = 1; i <= 90; i++) {
if (dp[i] > N) {
length = i - 1;
break;
}
}
while (length) {
if (dp[length] <= N) {
cout << 1;
N -= dp[length];
}
else {
cout << 0;
}
length--;
}
cout << '\n';
}
void input() {
cin >> N;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
init();
input();
solve();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 1520 내리막 길 (0) | 2021.03.28 |
|---|---|
| boj 1937 욕심쟁이 판다 (0) | 2021.03.28 |
| boj 2228 구간 나누기 (0) | 2021.03.21 |
| boj 1695 팰린드롬 만들기 (0) | 2021.03.20 |
| boj 9177 단어 섞기 (0) | 2021.03.19 |