문제

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

풀이

기초적인 그래프 탐색 문제이다. 8방향으로 그래프를 탐색해가며 총 컴포넌트(연결되어 있는 노드 집합)의 수를 구해주면 되는데 컴포넌트의 수를 구하기 위해서는 dfs를 몇 번 호출하는지 세어주기만 하면 된다.

방문할 땅과 연결된 모든 땅은 dfs를 통해 방문 표시가 될것이므로 dfs 호출할때 방문하지 않은 땅만 밟으면 총 섬의 개수를 구할 수 있다.

#include<stdio.h>
#include<string.h>
int map[51][51], visit[51][51],w,h;
int dfs(int y,int x){
	int i,j;
	visit[y][x] = 1;
	for(i=-1;i<=1;i++){
		for(j=-1;j<=1;j++){
			if(y+i<1 || x+j<1 || y+i>h || x+j>w) continue;
			if(!visit[y+i][x+j] && map[y+i][x+j])
				dfs(y+i,x+j);
		}
	}
}
int main(){
	while(1){
		int i,j,island=0;
		scanf("%d%d",&w,&h);
		if(!w&&!h) break;
		for(i=1;i<=h;i++){
			memset(map[i],0,sizeof(map[i]));
			memset(visit[i],0,sizeof(visit[i]));
			for(j=1;j<=w;j++)
				scanf("%d",&map[i][j]);
		}
		
		for(i=1;i<=h;i++){
			for(j=1;j<=w;j++){
				if(!visit[i][j] && map[i][j]){
					dfs(i,j);
					island++;
				}
			}
		}
		printf("%d\n",island);
		
	}
}

문제

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일때 경우의 어느정도 있는지 이미 알고있다.

• 1

• 1+1
• 2

• 1+1+1
• 1+2
• 2+1
• 3

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