[백준 알고리즘] 2193번 이친수

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

2193번: 이친수

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

 

풀이

아마 옛날의 내가 풀었으면 단순히 for문을 통해서 어떠한 Index값이 1이면 그 다음 값도 비교해서 1이 중복된다면 count 추가 후 전체 숫자에서 빼주는 형태로 풀었을 것 같다.

int Num =1000000111000;

String StrNum = to_string(Num);

for(int i=0; i< StrNum.size()-1; i++){
	if(strNum[i] =='1') {
    	if(strNum[i+1] == '1') {
        	count++;
            continue;
        }
    }
}

answer = Num -count;

cout<< answer<<endl;

 

하지만 이런 유형을 자주 겪다보니 DP 유형으로 풀면 시간복잡도에서도 유리한 점을 알 수 있어서 이번 문제는 DP로 풀게 되었다.

이 문제의 조건은 다음과 같다. 

 

1) 0으로 시작하지 않는다. => 해당 int값이 들어오면 자릿수가 자동으로 적어지므로 생각하지 않았다.

2) 1이 두번 연속오지 않는다 

 

2번 조건을 생각해보면 어떠한 N번째 자리수라고 했을 때 마지막 숫자가 1인경우와 0인 경우 두개를 생각해볼 때의 경우의 수가 주어진다.

 

- 마지막 숫자가 1인 경우 -> 그 전 자리 숫자는 무조건 0이어야 한다. -> 전전 자리 숫자는 0 또는 1 아무거나 와도 상관없다.

 

- 마지막 숫자가 0인 경우 -> 그 전 자리의 숫자는 0 또는 1 아무거나 와도 상관없다.

 

 

이 두가지가 되는데 DP로 생각해보면
마지막 경우의 수 = 전 경우의 수(마지막값이 0일 때) + 전전 경우의 수 (마지막 값이 1일 때) 라는 식이 성립하게 된다.

 

한자리수의 경우의 수는 1개(1)이고, 두자리 수 경우의 수는 (10) 1개 이므로 3자리 수부터 DP를 활용하여 식을 세울 수 있다.

 

단, 문제에서 90자리까지 생각하므로 10^90을 넘어선다. 그렇기 때문에 int가 아닌 long으로 설정해야한다. (이 것때문에 한번 틀림.. INT 범위 생각할 것)

 

#include<iostream>

using namespace std;


int main() {

	long Kind[91] = { 0 }; //자릿수별 경우의 수
	int Num = 0; //자릿수
	cin >> Num;

	Kind[1] = 1; // 자릿수가 1개일 때 경우의 수 1
	Kind[2] = 1; // 자릿수가 2개일 때 경우의 수 2

	for (int i = 3; i <= Num; i++) {
		Kind[i] = Kind[i - 1] + Kind[i - 2]; // 전 경우의 수  + 전전 경우의 수
	}

	cout << Kind[Num] << endl;

	
	

 

 

 

 

끝.