알고리즘/백준 풀이(동적 프로그래밍)
백준 2193번 - 이친수
공부 기록장
2024. 1. 9. 22:16
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
다음 문제는 경우의 수를 모두 작성하여 규칙을 본 결과 피보나치 배열과 같다는 걸 알게 되었다.
N자리 이친수의 개수는 다음과 같다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
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]);
}
}