👩🏻‍💻 문제링크

https://www.acmicpc.net/problem/2193

2193번: 이친수

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않

www.acmicpc.net

✍️ 아이디어

1. 문제 이해

0과 1로 이루어진 수인데 1이 연속해서 나오면 안됨
0으로 숫자가 시작하면 안됨

2. 2차원 dp로 끝자리가 0인 경우와 1인경우를 나눔

0인 경우는 이전 자리수에서 끝이 0,1 둘다와도 되고 1인경우는 이전 자리수에서 끝에가 0이 나와야함

✍️소스코드

내코드(2차원 dp 사용)

#include <iostream>
using namespace std;
long long result[100][2];

int main()
{
	int n; cin>>n;
	result[1][1]=1;
	for(int i=2; i<=n; i++)
	{
		result[i][0]=result[i-1][0] + result[i-1][1]; //핵심
		result[i][1]=result[i-1][0]; //핵심2
	}
	cout<<result[n][0] + result[n][1]<<'\n';
}

다른 사람 코드 (0과 1로만 나뉘는것이기 때문에 1차원 dp로도 풀수는 있음)

#include <iostream>
using namespace std;
long long d[91];
int main() {
    int n;
    cin >> n;
    d[1] = 1;
    d[2] = 1;
    for (int i=3; i<=n; i++) {
        d[i] = d[i-1] + d[i-2]; //맨 마지막이 0인경우 + 맨 마지막이 01인 경우 (01을 세트로 묶어)
    }
    cout << d[n] << '\n';
    return 0;
}

체감난이도	걸린시간	참고	사용 문법
하	10min	x	2차원 dp