[백준 2193] 이친수

문제 출처

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

2193번: 이친수

어떻게 풀어야할까

먼저 이친수의 특징을 살펴보자

1. 0으로 시작하지 않는다.

2. 1이 연속으로 들어가지 않는다.

 

특징이 어렵지는 않지만 문제 풀이가 바로 떠오르지는 않는다.

이친수의 예시를 4자리 수까지 적어보자.

1

10

100

101

1000

1001

1010

 

적어보면 이친수 목록의 특징이 눈에 띈다.

잘 모르겠다면 이렇게 잘라보자.

1 |

-----

1 | 0

-----

10 | 0

10 | 1

-----

100 | 0

100 | 1

101 | 0

 

그렇다. N자리 이친수는 갑자기 툭 튀어나오는 게 아니다.

N-1자리 이친수에 0또는 1을 붙힌 수라는 것을 알 수 있다.

 

아이디어 적용

위에서 찾아낸 특징을 토대로 점화식을 작성할 수 있다.

 

마지막 이진수가 0 이면 [N][0]에 들어간다.

 

코드화

점화식을 코드로 바꾸는 건 아주 쉽다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	cin.sync_with_stdio(false);
	int n; cin >> n;
	
	vector<vector<int>> pinary(n+1, vector<int>(2, 0));
	
	pinary[1][0] = 0;
	pinary[1][1] = 1;
	
	for (int i = 2; i <= n; ++i)
	{
		pinary[i][0] = pinary[i-1][0] + pinary[i-1][1];
		pinary[i][1] = pinary[i-1][0];
	}
	
	cout << pinary[n][0] + pinary[n][1] << endl;
}

이대로 돌려보면, 컴파일 또는 런타임 에러가 발생하지 않는다.

하지만 정답아니다.

n에 최대값을 넣어보면 이유를 알 수 있다.

 

결과:

int로 표현이 제대로 되지 않고 있다.

 

int 자료형으로는 한계가 있다. 코드 안의 모든 int를 long으로 바꿔주자.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	cin.sync_with_stdio(false);
	int n; cin >> n;
	
	vector<vector<long>> pinary(n+1, vector<long>(2, 0));
	
	pinary[1][0] = 0;
	pinary[1][1] = 1;
	
	for (int i = 2; i <= n; ++i)
	{
		pinary[i][0] = pinary[i-1][0] + pinary[i-1][1];
		pinary[i][1] = pinary[i-1][0];
	}
	
	cout << pinary[n][0] + pinary[n][1] << endl;
}

 

정리

결과 코드의 복잡도는 for문만 보면 되고,

그에 따르면 O(N)으로 꽤 빠른 알고리즘이다.

 

풀이방식은 다이나믹 프로그래밍을 사용했다.