backjoon - 2193 번 [ 이친수 ]

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

2193번: 이친수

 

 

문제는 다음과 같당

 

 

 

 

이 문제에서 요구하는 조건을 보면 이친수는 0으로 시작하여서는 안되고, 1이 연속으로 두 번 이상 나타나서는 안된다. 즉, 예시에서와 

같이 0010101과 같이 0으로 시작하거나, 101101과 같이 1이 연속으로 나와서는 안된다. 즉, 이 두 조건을 만족하는 N자리 이친 수를 구해야 한다. 만약 N이 1일 경우 이친 수는 1 밖에 없을 꺼고 N이 2일 경우 이친수는 10밖에 없을 것이다.( 01이나 11은 올 수 없으니깐 ) 또한 마찬가지로 N이 3일 경우는 100과 101이 올 수 있을 것이다. 

 

 

이제 본격적으로, 이 문제를 해결하는 방법에 대해 설명해 보면, 이친수가 0으로 끝나는 경우와 1로 끝나는 경우로 나누어서 해결을 하면 된다. N이 2일때의 이친수를 구하는 예시를 들면, 먼저 맨 처음 1자리 수에서  1로 끝나는 이친수는 1 자신 밖에 없으므로 1개가 있고, 0으로 끝나는 이친수는 하나도 없으므로, 1로 끝나는 이친수 1개와 0으로 끝나는 이친수 0개가 있다. 다음 2자리 수(즉 10의 자리 수)에서 이친수를 구하는 방법은 이전 자릿 수 에서 구한 이친수들 맨 뒤에다가 저 문제의 조건에 맞게 0와 1를 붙여주면 된다. 1의 자릿수에서 나오는 이친수는 1밖에 없다. 연속으로 1이 두 번 나타날 수 없으므로, 1뒤에다가 붙을 수 있는 수는 0밖에 없다. 즉, 2자리 수에서 나오는 이친수는 10밖에 없으므로, 1로 끝나는 이친수 0개와 0으로 끝나는 이친수 1개가 있다. 마지막으로, N이 3일때 3자릿수(즉 100의 자리 수)를 구해보자면, N-1자리 수 이친수 에다가 아까 말했던 것 처럼 조건에 맞게 0과 1을 붙여주면 된다. 즉, 맨 처음 1의 자리 일때는 이친수가 1 밖에 안 나왔고, 다음 2자리 일때는 1의 자리 에서 구한 이친수 1에다가 0을 붙여 주어 10을 만들었다. 

 

 

 이친 수 10 뒤에는 0도 붙을 수 있고, 1도 붙을 수 있으므로( 1이 연속으로 붙질 않으니까 ) 0으로 끝나는 이친수 100과 1로 끝나는 이친수 101이 나올 수 있다. 만약 4자릿 수 까지 구한다면, 이전 3자리 이친수 100과 101에서 먼저 100에는 뒤에 0이 붙을 수 도 있고,

1이 붙을 수도 있으므로, 1000과 1001이 나온다. 그리고 101에는 뒤에 0밖에 못 붙으므로, 1010이 나온다. 즉 4자리 수 이친 수는 총 0으로 끝나는 수 0개와 1로 끝나는 수 2개가 나오는 것을 확 인 할 수 있다. 

 

 

0으로 끝나는 이친수	없음	10	100	1000, 1010	10000, 10100, 10010,
1로 끝나는 이친수	1	없음	101	1001	10001 ,10101
자릿수	N=1	N=2	N=3	N=4	N=5

 

 

위와 같이 N이 5일 때까지의 이친 수를 정리해 보면 다음과 같다. N번째 0으로 끝나는 이친 수는 N-1 번째 0으로 끝나는 이친수나 1로 끝나는

이친 수에다가 모두 뒤에 0만 붙여주면 구 할 수 있고, 1로 끝나는 이친수는 이전 N-1번째 이친수의 0으로 끝나는 이친수에다가 1만 붙여주면 구할 수 있다.

 

 

즉, N자릿수 이친 수를 구할려면 N자리의 0으로 끝나는 이친수는 N-1의 0으로 끝나는 이친수 + N-1의 1로 끝나는 이친수를 더한 값이

될 거고, N자리의 1로 끝나는 이친 수를 구할려면 N-1의 0으로 끝나는 이친수를 넣어주면 된다. 즉 N의 1로 끝나는 이친수와 0으로 끝나는 이친수를 더하면 최종적으로 N자리수 이친수를 구 할 수 있을 것이다. 나는 일부러 배열을 사용하지 않고 그냥 unsigned long long 자료형 두 개로 문제를 해결하기 위해  기존  1로 끝나는 이친수 가 1개이고  0으로 끝나는 이친수가 2개일 때 '1로 끝나는 이친수' = '1로 끝나는 이친수 '+ '0으로 끝나는 이친수' 한다음 stl의 swap 함수를 통해 1로 끝나는 이친수와 0으로 끝나는 이친수에 들어 있는 값을 swap 하였다.

 

내가 짠 코드는 다음과 같다.

 

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(){
   
    int N=0;
    unsigned long long one=1;
    unsigned long long zero=0;
    
    cin >> N;
    
    if(N==1){
        cout << 1 << endl;
    }
    else{
        for(int i=0;i<N-1;i++){
            if(zero!=0){
                one+=zero;
            }
           
            swap(one,zero);
        }
        
        cout << one+zero << endl;
    }
    
    return 0;
}
 

 

 

위와 같이 따로 0으로 끝나는 이친수 , 1로 끝나는 이친 수의 개수를 저장하는 배열을 따로 만들지 않고 unsigned long long형 변수 2개 만들 사용 해 코드를 간결하게 작성해보았다.