[성실코딩 30일차] 백준 #1562 계단 수 **

모르겠다... 규칙성 있을 것 같은데...

예를 들어, N=14일 경우,

"9~0"을 순서대로 놓는 10개를 제외하고, 4개를 정렬하는 경우의 수를 따졌다.

1) "9~0" _ _ _ _

2) _ _ _ _ "9~0"

3) _ _ _ "9~0" _

4) _ _ "9~0" _ _

5) _ "9~0" _ _ _

이렇게 놓는 방법을 생각했고, 각각 6개, 6개, 3개, 3개, 4개가 가능하다.

그리고 4개 자리 수에서 5개 자리 수로 증가할 때마다, 4개에 수에서 각각 2가지 경우가 추가로 가능하다. ( 끝자리 수인 0이나 9를 제외하고)

왜냐하면 예를들어 마지막 자리수가 4로 끝날 경우, 그 뒤에 값을 추가해주려고 하면 ( _ _ _ 4 ), 3혹은 5가 가능하기 때문. ( _ _ _  4 5, _ _ _ 4 3 )

(반면 0이나 9는 그 다음 올 수 있는 숫자가 1과 8 각각 하나밖에 없음.)

#include < iostream >

using namespace std;

unsigned long long sum = 0;
int n;

int main(void) {
	
	// 입력
	cin >> n;

	if (n<10) {
		cout << "0" << endl;
	}
	else if (n == 10) {
		cout << "1" << endl;
	}
	else {
		int ans = 1;
		
		for (int i = 1; i <= n - 10; i++) {
			if (i%2==0) { // 짝수
				ans = ans << 1;
				ans = ans + i / 2;
			}
			else {  // 홀수
				ans = ans << 1;
			}
			ans = ans % 1000000000;
			sum += ans;
		}

		cout << sum << endl;
		//cout << ans << endl;
	}

	return 0;
}