[C/C++] 백준 2193번 - 이친수 (DP)

 

 

<코드>

#include<iostream>
#include<algorithm>
using namespace std;

long long n, dp[1001];

int main()
{
	dp[1] = 1;
	dp[2] = 1;
	dp[3] = 2;
	cin >> n;

	for (int i = 3; i <= n; i++)
	{
		dp[i] = 1; // 1000....0 과 같은 경우의 수
		for (int j = 1; j <= i - 2; j++)
		{
			dp[i] += dp[j];
		}
	}
	cout << dp[n];
}

 

풀이 방법

 

4자리 수

• 1000
• 1001
• 1010

dp[4] = 1 + dp[1] + dp[2]

 

5자리 수

• 10000
• 10001
• 10010
• 10100
• 10101

dp[5] = 1 + dp[1] + dp[2] + dp[3]

 

6자리 수

• 100000
• 100001
• 100010
• 100100
• 100101
• 101000
• 101001
• 101010

dp[6] = 1 + dp[1] + dp[2] + dp[3] + dp[4]

 

www.acmicpc.net/problem/2193

2193번: 이친수