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));
    }
}