<div id="readability-page-1" class="page"><article><header><time datetime="December 18, 2017">December 18, 2017</time><a rel="tag" href="/tags#다이나믹-프로그래밍">#다이나믹 프로그래밍</a> <a rel="tag" href="/tags#백준온라인저지">#백준온라인저지</a> </header><section><a href="https://www.acmicpc.net/problem/9507" target="_blank" rel="noopener">9507번 Generations of Tribbles</a>
해당문제는 시간 제한이 2초이므로 <a href="/algo/2016/05/15/Algo0-dynamic-programing/">다이나믹프로그래밍</a>으로 풀어야한다. 완전 탐색으로 풀 경우 시간이 초과된다.
<div data-language="cpp"><pre><code>#include &lt;cstdio&gt;

long long koong(int n);
long long num[77];

int main(){
	num[0]=1;
	num[1]=1;
	num[2]=2;
	num[3]=4;

	int n,t;
	scanf("%d",&amp;t);

	while(t--){
		scanf("%d",&amp;n);
		printf("%llu\n",koong(n));
	}

	return 0;
}

long long koong(int n){
	if(num[n] != 0)return num[n];
	num[n] = koong(n-1)+koong(n-2)+koong(n-3)+koong(n-4);
	return num[n];
}</code></pre></div></section><hr></article></div>

Kimlog RSS Feed

KIM, WOOJUNG

9507번 Generations of Tribbles
해당문제는 시간 제한이 2초이므로 다이나믹프로그래밍으로 풀어야한다. 완전 탐색으로 풀 경우 시간이 초과된다.
#include <cstdio>
long long koong(int n);
long long num[77];
int main(){
	num[0]=1;
	num[1]=1;
	num[2]=2;
	num[3]=4;
	int n,t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		printf("%llu\n",koong(n));
	}
	return 0;
}
long long koong(int n){
	if(num[n] != 0)return num[n];
	num[n] = koong(n-1)+koong(n-2)+koong(n-3)+koong(n-4);
	return num[n];
}

9507번 Generations of Tribbles

댓글