알고리즘/백준
[백준]2193. 이친수
김수진장
2020. 10. 29. 21:13
[문제]
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
[풀이]
N이 1인 경우부터 모든 경우의 수를 구하다 보면 규칙을 금방 발견할 수 있다.
규칙을 통해 아래와 같이 점화식을 세워서 DP를 사용해 풀었다.
DP[i] = DP[i-1]+DP[i-2];
[코드]
시간 : 0ms
#include <iostream>
#define MAX 90
using namespace std;
long long DP[MAX]={0,};
int N;
int main(void)
{
cin >> N;
DP[1] = 1;
DP[2] = 1;
for(int i=3;i<=N;i++)
{
DP[i] = DP[i-1]+DP[i-2];
}
cout << DP[N];
return 0;
}