침대 밖은 위험해!

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

1. 문제요약

- 주어진 정수를 1, 2, 3 의 합으로 나타내는 방법의 수는?

- 1 <= n <= 11

- 4를 1, 2, 3의 조합으로 나타내는 방법 7가지

  1 + 1 + 1 + 1

  1 + 1 + 2

  1 + 2 + 1

  2 + 1 + 1

  2 + 2

  1 + 3

  3 + 1

2. 접근방법

- 임의의 정수 n을 1, 2, 3의 조합으로 나타내는 가짓수는

  n-1을 1, 2, 3의 조합으로 나타내는 가짓수 +

  n-2를 1, ,2, 3의 조합으로 나타내는 가짓수 +

  n-3을 1, 2, 3의 조합으로 나타내는 가짓수

- d[n] : n을 1, 2, 3의 조합으로 나타내는 가짓수 로 정의한다면

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

3. 시간복잡도

- n

4. 회고

- 문제를 분할, 임의의 수에서 문제를 잘게 쪼개 보자

소스코드

#include<iostream>
using namespace std;

int t, n, d[11] = { 0, 1, 2, 4 };

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

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

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

1. 문제요약

- 2xn 크기의 직사각형을 1x2, 2x1, 2x2 타일로 채우는 방법의 수는?

- 1 <= n <= 1,000

- 10007로 나눈 나머지를 출력

2. 접근방법

- 2xn 도형을 채우는데 n번째에 올 수 있는 모형의 종류는

  세로 1x2 1개

  가로 2x1 2개

  정사각형 2x2 1개

  가 올 수 있음

- d[n]을 2xn 모형을 채우는 경우의 수 라고 하면

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

3. 시간복잡도

- n

4. 회고

소스코드

#include<iostream>
using namespace std;

int n, d[1001] = { 0, 1, 3 };

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

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

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

1. 문제요약

- 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수는?

- 1 <= n <= 1,000

- 10007로 나눈 나머지를 출력

2. 접근방법

- 2xn 도형을 채우는데 n번째에 올 수 있는 모형의 종류는

  세로 1x2 1개

  가로 2x1 2개

  가 올 수 있음

- d[n]을 2xn 모형을 채우는 경우의 수 라고 하면

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

  피보나치

3. 시간복잡도

- n

4. 회고

- 모듈러 연산 : https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction

소스코드

#include<iostream>
using namespace std;

int n, d[1001] = { 0, 1, 2 };

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

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