[C++] BAEKJOON (2193) 이친수

문제

0과 1로만 이루어진 수를 이진수라 한다.

이러한 이진수 중 특별한 성질을 갖는 이친수(pinary number)가 있는데, 이친수는 다음 성질을 만족한다.

 

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다.

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

 

 

풀이

N은 이진수 자릿수를 나타낸다.

각 자릿수에 대한 이친수의 개수를 계산하면,

N이 1일 경우(N=1), "1" 하나의 수만 올 수 있다.

N이 2일 경우(N=2), '1' 다음에 "0" 하나의 수만 올 수 있다.

N이 3일 경우(N=3), '0' 다음에 "1", "0" 두 가지의 수가 올 수 있다.

...

 

'1' 뒤에는 "0" 하나의 수만 올 수 있고, '0' 뒤에는 "1" 또는 "0"이 올 수 있다.

 

N	1	2	3	4	5	6	7	...	N
	1	0	1	0	1	0	1
							0
					0	1	0
						0	1
							0
			0	1	0	1	0
						0	1
							0
				0	1	0	1
							0
					0	1	0
						0	1
							0
이친수	1	1	2	3	5	8	13	...	(N-2 경우의 수) + (N-1 경우의 수)

 

"0"은 항상 올 수 있다. 'N-2' 이친수 개수는 'N-1'에 존재하는 "0"의 개수가 된다.

'N-1'에 존재하는 "0"의 개수만큼 'N' 자릿수에 존재하는 이친수의 개수가 증가한다.

 

N = ('N-1' 이친수 개수) + ('N-1' 0의 개수) = ('N-1' 이친수 개수) + ('N-2' 이친수 개수)

 

#include <iostream>

int main(void){

  using namespace std;

  int N;
  cin >> N; // 1 <= N <= 90

  long long res = 1;		// 이친수 개수
  long long tmp, caseN2 = 1;

  for(int i = 3; i <= N; ++i){
    tmp = res;		// N-1 경우의 수를 tmp에 저장한다.
    res += caseN2;	// N 자릿수 이친수의 개수를 구한다. (res: N-1, caseN2: N-2)
    caseN2 = tmp;	// N-2 경우의 수를 caseN2에 저장한다. ('N-1'이 'N-2'가 된다.)
  }

  cout << res;

  return 0;
}

 

 

 

주의

데이터 자료형이 표현할 수 있는 크기에 주의하여야 한다.

N이 일정 값을 넘어가면, int로 표현할 수 있는 수의 범위를 넘어가게 되어 오류(오버플로우; overflow)가 발생한다.

 

 

 

출처 : BAEKJOON