[Algo Rhythm🕺💃] BOJ 9095 - 1, 2, 3 더하기

💫문제 분석

테스트 케이스의 개수를 $t$, 각 테스트 케이스마다 주어지는 정수를 $n (1 \le n \lt 11)$이라고 하자. 그리고 $n$을 $1,\ 2, \ 3$의 합으로 나타내는 방법의 수를 $f(n)$이라고 하자.

각 테스트케이스마다 $f(n)$을 출력해야 하며, 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

$f(n)$은 1부터 차례대로 아래와 같다. 이때 파란색 동그라미로 표시된 수들을 관찰하면 분명히 연쇄적인 관계가 있다는 것을 알 수 있다. 따라서 이 문제는 그 '연쇄적인 관계'를 이용하여 해결할 수 있다.

 

 

🔥문제 풀이

앞서 언급한 연쇄적인 관계는 다음과 같다.

 

$\begin{matrix} f(i) &=& \sum_{j = 1}^3 g(i, j) & (1\le i\lt 11, i \in Z) \\ g(i, j) &=& \begin{cases}0, & i - j < 0\\1, & i - j == 0\\f(i - j), & i - j > 0\\ \end{cases} \end{matrix}$

 

$f(i)$를 저장하는 배열을 만든 뒤 이 식을 이용하여 bottom-up 방식으로 계산한 뒤 저장하면 된다.

 

✨복잡도 분석

테스트 케이스의 개수를 $t$, 각 테스트 케이스마다 주어지는 정수를 $n (1 \le n \le 11)$이라고 할 때, 시간 복잡도와 공간 복잡도는 다음과 같다.

 

⏰시간 복잡도 : $O(t + n)$

$f(n)$을 저장하는 배열을 만드는데 $O(n)$이 소요됨.

테스트 케이스의 개수만큼 $f(n)$을 출력해야 하기 때문에 $O(t)$가 소요됨.

따라서, 전체적인 시간 복잡도는 $O(t + n)$임.

🏠공간 복잡도 : $O(n)$

$f(n)$을 저장하는 배열을 만드는데 $O(n)$이 소요됨.

 

🌈코드

	#include <cstdio>
	int f[11];
	int main()
	{
	int t, n, tmp;
	scanf("%d", &t);
	for(int i = 1; i < 11; i++)
	{
	tmp = 0;
	for(int j = 1; j <= 3; j++)
	{
	if(i - j < 0) break;
	if(i - j) tmp += f[i - j];
	else tmp += 1;
	}
	f[i] = tmp;
	}
	for(int i = 0; i < t; i++)
	{
	scanf("%d", &n);
	printf("%d\n", f[n]);
	}
	return 0;
	}

view raw boj9095.cpp hosted with ❤ by GitHub

 

🌏문제 출처

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기