Mystika+Algorithm

BOJ 9095 - 1, 2, 3 더하기

알고리즘/동적 계획법

문제

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



풀이

이제 막 알고리즘에 입문한 알린이 친구 김X를 위해 쓰는 풀이. 사실 나도 흐접인데 X호는 더 흐접이라 많이 도와줘야된다. 원래 못하는 애들끼리 도우면서 살랬음.



정수 N을 1,2,3의 합 조합으로 나타낼수 있는 모든 경우의 수를 구하는게 목적이다. 문제를 역으로 생각해보면 우리는 N에서 항상 1, 2, 3을 빼는 선택지밖에 없으므로 점화식은 $ f(n) = f(n-1) + f(n-2) + f(n-3) $이다.


여기서 우리는 이미 N이 1~3일때 경우의 어느정도 있는지 이미 알고있다.


N=1일때
  • 1

N=2일때
  • 1+1
  • 2
N=3일때
  • 1+1+1
  • 1+2
  • 2+1
  • 3

이 점화식과 기저 사례를 통해 Bottom-Up과 Top-Down 풀이를 쉽게 작성할수 있다.


Bottom-Up

#include <stdio.h>
int main() {
	int n,t,i,j;
	int arr[11]={0};
	arr[1]=1;
	arr[2]=2;
	arr[3]=4;
	scanf("%d",&t);
  	while(t--){
    	scanf("%d",&n);
    	for(i=4;i<=n;i++){
    		if(arr[i]) continue;
    		arr[i]=arr[i-1]+arr[i-2]+arr[i-3];
    	}
    	printf("%d\n",arr[n]);
  	}
}


Top-Down

#include <stdio.h> #include <string.h> int cache[11]; int solve(int i){ if(!i) return 1; if(i<0) return 0; if(cache[i] != -1) return cache[i]; return cache[i] = solve(i-1) + solve(i-2) + solve(i-3); } int main(){ int n,t; scanf("%d",&t); memset(cache,-1,sizeof(cache)); while(t--) { scanf("%d",&n); printf("%d\n",solve(n)); } }


저작자 표시 비영리 변경 금지
신고