문제

풀이

이분 탐색 말고 다른 풀이 방법도 있을것 같은데 아 잘 모르겠다. 나는 멍청한가봐. 사실 이 풀이도 888ms로 아슬아슬하게 AC 받았다.

맨 처음에 이 문제를 접했을때는 그냥 막연하게 `해쉬테이블 같은걸 사용하면 편하겠다!`라는 생각으로 <map>을 사용했었는데 당연하게도 시간 초과가 나와서 그냥 때려치고 두달동안 묵혀두다가 지금 다시 풀어봤는데 그냥 <vector> + std::sort 이분 탐색으로 풀면 될것같아서 풀어봤는데 그대로 AC가 나왔다. STL <set>으로 풀어도 될것같은데 이건 안해봤다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		vector<int> seen;
		int n,m,i,x,left,right,mid,found;
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d",&x);
			seen.push_back(x);
		}
		sort(seen.begin(),seen.end());
		
		scanf("%d",&m);
		for(i=0;i<m;i++){
			scanf("%d",&x);
			found = 0;
			left = 0;
			right = n-1;
			while(left <= right){
				mid = (left+right)/2;
				if(x==seen[mid]){
					found = 1;
					break;
				}else if(x < seen[mid]) right = mid-1;
				else left = mid + 1;
			}
			printf("%d\n",found);
		}
	}
	return 0;
}

문제

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

풀이

처음으로 푼 이분 탐색 문제다. 항상 랜선을 자를수 있는 경우의 입력만 들어온다 가정하고 left를 1로, right를 가장 큰 랜선의 길이로 정한 뒤 입력받은 모든 랜선들을 mid 값(left+right를 2로 나눈 값)으로 나눈 몫을 변수에 더하고 만약 필요한 랜선의 갯수보다 같거나 많다면 ans 변수에 값을 넣고 가장 마지막에 ans 변수에 들어가있는 값을 출력하게 했다.

#include <stdio.h>
#define max(a,b) a>b?a:b
int main(){
	long long n,m[10000]={0},k,d,i,left=1,right=-1,mid,ans;
	scanf("%lld%lld",&n,&k);
	for(i=0;i<n;i++){
		scanf("%lld",&m[i]);
		right=max(right,m[i]);
	}
	while(left<=right){
		mid=(left+right)/2;
		d=0;
		for(i=0;i<n;i++) d+=m[i]/mid;
		if(d >= k){
			ans = mid;
			left = mid+1;
		}else{
			right = mid-1;
		}
	}
	printf("%lld",ans);
}

주의할 점

1. mid값으로 모든 랜선을 나눈 몫의 합이 K(필요한 랜선의 갯수)를 넘어가는 경우에도 답이 될 수 있다. 처음 제출때 이 부분을 간과하고 있다가 틀렸다.

문제

https://algospot.com/judge/problem/read/WEIRD

풀이

알고스팟 튜토리얼에 있는 문제. 얼마전까지만해도 이 문제 풀지도 못했는데 지금은 풀 수 있는걸 보면 0.1% 정도는 실력이 늘은것같다.

어떤 수 N이 주어질때 그 수가 Weird한 수인지 판별하는 문제인데, Weird 여부를 판별하려면 아래 두 조건 중 하나라도 만족해야한다.

• N의 진약수들 중 일부의 합으로 N을 만들수 없다.

• 모든 진약수들의 합이 N보다 크다.(greater than N)

문제에는 Weird하지 않은 수의 조건이 나와있고 위의 조건은 Weird한 수의 조건이므로 혼동하지 말기를 바란다.

서너번 정도 제출하는데 계속 WA가 나와서 코드를 다시 훑어보았더니 두번째 조건을 빼먹었다. 댓글을 보니까 나와 같은 사람이 한둘이 아니더라..

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int solve(vector<int> &v,int sum, int depth){
	if(sum == n)return 1;
	if(sum > n || depth<0) return 0;
	return solve(v,sum+v[depth],depth-1) || solve(v,sum,depth-1);
}
int main() {
	int t,i,sum,flag,divsum;
	vector<int> pd;
	scanf("%d",&t);
	while(t--){
		divsum=sum=0;
		pd.clear();
		scanf("%d",&n);
		for(i=1;i<n;i++){
			if(n%i==0){
				pd.push_back(i);
				divsum+=i;
			}
		}
		sort(pd.begin(),pd.end());
		puts(divsum <= n || solve(pd,0,pd.size()-1)?"not weird":"weird");
	}
	return 0;
}

문제

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