침대 밖은 위험해!

문제출처 : https://www.acmicpc.net/problem/2193

1. 문제요약

- 0과 1로 이루어진 수 중에 0으로 시작하지 않고 1이 두번 연속으로 나타나지 않는 수를 이친수

- 1, 10, 101 등은 이친수

- 01, 110 은 이친수가 아님

- n자리 이친수의 갯수는?

- 1 <= n <= 90

2. 접근방법

- n자리 이진수를 브루트 포스로 다 확인할 수 없음.

- n자리가 0이면, n-1 자리는 0, 1

  n자리가 1이면, n-1 자리는 0

- d[n][i] 를 n자리수, 마지막 수가 i인 이친수의 갯수라고 하면

  d[n][0] = d[n-1][0] + d[n-1][1]

  d[n][1] = d[n-1][0]

- 조금만 더 생각을 해보면

- n자리가 0이면, n-1 자리는 0, 1

  n자리가 1이면, n-1 자리는 무조건 0 이므로 n-2 자리에 0, 1

- d[n] 을 n자리수 이친수의 갯수라고 하면

  d[n] = d[n-1] + d[n-2]

  피보나치

3. 시간복잡도

- n

4. 회고

- 이친수의 갯수가 int형을 넘을 수 있으므로 long long

소스코드

#include<iostream>
using namespace std;

int n;
long long d[100] = { 0, 1 };

int main(void){
	cin >> n;
	for (int i = 2; i <= n; i++){
		d[i] = d[i - 1] + d[i - 2];
	}
	cout << d[n] << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/11057

1. 문제요약

- 33455, 012345와 같이 각 자릿수가 오름차순인 수를 오르막 수라 함.

- 인접한 수가 같아도 오름차순으로 인정

- 9111 과 같은 수는 오르막 수가 아님

- 수는 0으로 시작 할 수 있음

- 오르막 수의 갯수는?

- 1 <= n <= 1,000

2. 접근방법

- n자릿수가 1000 이므로 모든 수를 다 확인 할 수 없음

- n 자릿수의 마지막 수가 0 이면, n-1 자릿수의 마지막 수는 0

  n 자릿수의 마지막 수가 1 이면, n-1 자릿수의 마지막 수는 0, 1

  n 자릿수의 마지막 수가 2 이면, n-1 자릿수의 마지막 수는 0, 1, 2

  ...

- 필요한 항목은 자릿수, 마지막 수 이므로

- d[n][j] : n 자릿수, 마지막 수가 j인 오르막 수의 갯수

- d[n][j] = d[n-1][0] + d[n-1][1] + ... + d[n-1][j-1] + d[n-1][j] = ∑(i=0, j) d[n-1][i]

3. 시간복잡도

- n

4. 회고

- 10007의 나머지 이므로 n이 1000 이라 해도 1000자릿수의 10007의 나머지 합이 int 범위를 넘어 갈 수 없음

소스코드

#include<iostream>
using namespace std;

int n, d[1001][10], ans = 0;

int main(void){
	cin >> n;
	for (int i = 0; i < 10; i++) d[1][i] = 1;
	for (int i = 2; i <= n; i++){
		for (int j = 0; j < 10; j++){
			for (int k = 0; k <= j; k++){
				d[i][j] += d[i - 1][k];
			}
			d[i][j] %= 10007;
		}
	}
	for (int i = 0; i < 10; i++) ans += d[n][i];
	cout << ans % 10007 << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/10844

1. 문제요약

- 45656 은 인접한 모든 자리수의 차이가 1 이를 계단수라 함

- n 자리수의 계단수의 갯수는?

- 한자릿수는 9개

2. 접근방법

- 100 자릿수 이므로 브루트 포스는 못함

- dp를 활용

- n-1 자릿수의 마지막 수가 0 이면, n 자릿수의 마지막 수는 -1, 2 인데 -1은 아니므로 2

  n-1 자릿수의 마지막 수가 1~8이면, n 자릿수의 마지막 수는 n-1의 마지막 수 -1, +1

  n-1 자릿수의 마지막 수가 9 이면, n 자릿수의 마지막 수는 8, 0 인데 0은 아니므로 8

- dp에 필요한 항목은 '자릿수', '마지막수'

- d[n][j] : n 자릿수의 마지막 수가 j인 갯수

- 일반적으로 d[n][j] = d[n-1][j-1] + d[n-1][j+1]

3. 시간복잡도

- n

4. 회고

- d[n][j] = d[n-1][j-1] + d[n-1][j+1] 을 j가 0일 때와 9일때로 나누지 않은 이유는

  전역변수로 선언시 d[n][-1] 은 0으로 해주기 때문(음수 인덱스)

- 정답이 1,000,000,000 로 나눈 나머지 이므로 d[n][0] ~ d[n][9] 까지의 합이 int 범위를 넘어 갈 수 있으므로

  ans는 long long으로 선언

- d[101][11]이 아닌 d[101][10] 으로 선언하면 d[n][10] 인경우 인덱스가 넘어가서 다른 값이 나옴

소스코드

#include<iostream>
using namespace std;

int n, d[101][11];
long long ans = 0;

int main(void){
	cin >> n;
	for (int i = 1; i < 10; i++) d[1][i] = 1;
	for (int i = 2; i <= n; i++){
		for (int j = 0; j < 10; j++){
			d[i][j] = (d[i - 1][j - 1] + d[i - 1][j + 1]) % 1000000000;
		}
	}
	for (int i = 0; i < 10; i++) ans += d[n][i];
	cout << ans % 1000000000 << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]