[DP] 백준 문제 풀이 - 2193 이친수

👩🏻‍💻 문제링크

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

2193번: 이친수

 

✍️ 아이디어

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