2193 이친수 (조합론, 동적 계획법) [Silver III]

2193번: 이친수 (acmicpc.net)

 

0과 1로 이루어진 N개의 이친수를 구하는 문제입니다.

조건 1. 0으로 시작하지 않음,

조건 2. 1이 두 번 연속으로 나타나지 않음

 

이친수 예시

1, 10, 100, 101, 1000, 1001, 1010 

 

 

풀이법

이 문제는 조합식을 이해하는데 아주 좋은 문제라고 생각합니다.

여러 방법으로 풀 수 있으며 여러 조합식을 만들어서 본인만의 방법으로 풀이가 가능합니다.

 

저는 이 문제를 처음 풀 때 우선 경우의 수를 찾는 패턴을 구하기 위해

N이 1일때 부터 6일때 까지의 예시를 적어놓고 고민해보았습니다.

// 1                                                
// 10 
// 100, 101 
// 1000, 1001, 1010 
// 10000, 10001, 10010, 10100, 10101 
// 1000 00, 1000 01, 1000 10, 1001 00, 1001 01, 1010 00, 1010 01, 1010 10

 

처음 제가 찾은 패턴은 이러합니다.

 

N이 3일 때의 경우의 수는 1일 때의 경우의 수 + 1

N이 4일 때의 경우의 수는 2일 때의 경우의 수 + 1일 때의 경우의 수 + 1

N이 5일 때의 경우의 수는 3일 때 + 2일 때 + 1일 때 + 1

N이 6일 때의 경우의 수는 4일 때 + 3일 때 + 2일 때 + 1일 때 + 1

 

즉

N자리 이친수의 경우의 수 = 1 ~ (N - 1) 까지의 경우의 수의 합 + 1

 

위 공식을 통해 구현한 첫 번째 정답 코드입니다.

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	D.resize(N + 2, 0);
	
	D[1] = 1;
	D[2] = 1;

	for (int i = 3; i <= N; i++)
	{
		for (int j = 1; j < i - 1; j++) {
			D[i] += D[j];
		}
		D[i]++;
	}

	cout << D[N];
}

 

 

정답을 맞추고 다시 생각해보니 재밌는 사실을 하나 발견했습니다.

// 끝이 1인 갯수, 끝이 0인 갯수
// (1, 0) 1                                                
// (0, 1) 10 
// (1, 1) 100, 101 
// (1, 2) 1000, 1001, 1010 
// (2, 3) 10000, 10001, 10010, 10100, 10101 
// (3, 5) 1000 00, 1000 01, 1000 10, 1001 00, 1001 01, 1010 00, 1010 01, 1010 10

 

 

끝이 1인 갯수와 끝이 0인 갯수를 통해 조합식을 하나 만들 수 있다는 것 이었습니다.

N이 3일 때 끝이 1인 갯수 = 2일 때 끝이 1인 갯수 + 1일 때 끝이 1인 갯수
N이 3일 때 끝이 0인 갯수 = 2일 때 끝이 0인 갯수 + 1일 때 끝이 0인 갯수

 

위 공식을 통해 구현한 두 번째 정답 코드입니다.

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); 
	cout.tie(NULL);

	cin >> N;

	D[1][1] = 1; 
	D[1][0] = 0;  


	for (int i = 2; i <= N; i++)
	{
        D[i][1] = D[i - 1][1] + D[i - 2][1]; 
        D[i][0] = D[i - 1][0] + D[i - 2][0]; 
	}

	 
	cout << D[N][0] + D[N][1];

}

 

 

 

두 번째로 정답을 맞추고 패턴 하나를 더 발견했습니다.

// 끝이 1인 갯수, 끝이 0인 갯수
// (1, 0) 1                                                
// (0, 1) 10 
// (1, 1) 100, 101 
// (1, 2) 1000, 1001, 1010 
// (2, 3) 10000, 10001, 10010, 10100, 10101 
// (3, 5) 1000 00, 1000 01, 1000 10, 1001 00, 1001 01, 1010 00, 1010 01, 1010 10

 

N 자리 이친수의 끝이 0인 개수가 N + 1 이친수의 끝이 1인 개수로 이어지고

N 자리 이친수의 끝이 0인 개수와 1인 개수의 합이 N + 1 이친수의 끝이 0인 개수로 이어진다는 것 입니다.

즉 

N이 2일 때 끝이 1인 갯수 = 1일 때 끝이 0인 갯수
N이 2일 때 끝이 0인 갯수 = 1일 때 끝이 1인 갯수 + 1일 때 끝이 0인 갯수

 

위 공식을 통해 구현한  번째 정답 코드입니다.

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); 
	cout.tie(NULL);

	cin >> N;

	D[1][1] = 1; 
	D[1][0] = 0;  
	 
	for (int i = 2; i <= N; i++)
	{
		D[i][1] = D[i - 1][0];
		D[i][0] = D[i - 1][1] + D[i - 1][0];
	} 

	cout << D[N][0] + D[N][1];
}

 

 

조합식 문제가 나오면 항상 예시를 적어보는걸 추천합니다.

그 예시를 보고 패턴을 구해낼 수만 있다면 문제는 쉽게 해결됩니다.

감사합니다.