Algorithm/백준
[백준] 2193번 이친수
sirius
2021. 3. 5. 09:35
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 0 | 10 | 100 | 1000 1010 |
10000 10010 10100 |
100000 100010 100100 101000 101010 |
1000000 1000010 1000100 1001000 1001010 1010000 1010010 1010100 |
|
| 1 | 1 | 101 | 1001 | 10001 10101 |
100001 100101 101001 |
1000001 1000101 1001001 1010001 1010101 |
dp[6][0] = dp[5][0] + dp[5][1] : dp[5] 와 같음
dp[6][1] = dp[5][0] : dp[4] 와 같음
dp[6] = dp[5] + dp[4]
점화식 : dp[N] = dp[N-1] + dp[N-2]
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
long[] dp = new long[N + 1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= N; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
System.out.println(dp[N]);
}
}