[C]백준_2193 : 이친수

2022년 12월 1일에 작성됨

 

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

2193번: 이친수

 

 

 

문제 분석

N	이친수	이친수 개수
1	1	1
2	10	1
3	100, 101	2
4	1000, 1001, 1010	3
5	10000, 10001, 10010, 10100, 10101	5
...	...	...

 

규칙을 찾아보면
이친수의 개수 = (전전 이친수 + 전 이친수)의 개수가 된다.

 

 

 

소스 코드 (⭕)

#include <stdio.h>

int main()
{
	int i, n;
	long long DP[91] = { 0 };
	
	scanf("%d", &n);

	DP[1] = 1;
	DP[2] = 1;

	for (i = 3; i <= n; i++)
	{
		DP[i] = DP[i - 2] + DP[i - 1];
	}
	printf("%lld\n", DP[n]);

	return 0;
}

 

코드 분석

1. 경우의 수를 더하는 과정에서 결과값이 엄청 커질 수 있기 때문에 배열의 자료형을 long long으로 선언해주고 0으로 초기화 해준다.

2. n을 입력받고, 인덱스 1과 2의 요소 값을 1로 설정해준다.

3. for문으로 i는 3부터 n까지 반복해주어 DP[n] = DP[n-2] + DP[n-1] 식을 구해준다.

4. 배열을 long long 형으로 선언해줬기 때문에 %lld 형식으로 n자리 이친수의 개수인 DP[n]을 출력한다.

 

 

 

end

문제를 검색해보니 배열 이름을 DP로 해놓은 분들이 많아서 DP가 뭐지 싶었는데 다이나믹 프로그래밍의 줄임말이었다ㅋㅋㅋ!