문제

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

문제

풀이

Coin Change라는 이름으로 유명한 DP 문제이다. 이 문제는 2차원 배열을 사용해서 해결할수도 있고 1차원 배열을 사용해서 해결할수도 있는데 2차원 배열 사용하면 6MB 정도의 메모리를 사용하게 되므로 문제의 메모리 제한을 초과하게 된다. 

일단 2차원 풀이법부터 설명해보자면, dp[n][k] = n 종류의 동전으로 k원을 만드는 경우의 수라고 정의할때 dp[n][k]를 구하는 방법은 두가지이다.

1. dp[n][k-coin[n]] = n번째 동전을 사용한 뒤 k원을 만들수 있는 경우의 수

2. dp[n-1][k] = n번째 동전을 사용하지 않고 k원을 만들수 있는 경우의 수

이렇게 되므로 점화식은 $ dp[n][k] = dp[n][k-coin[n]] + dp[n-1][k] $가 된다.

#include<stdio.h>
#include<string.h>
int coin[100]={0},cache[100][10001];
int solve(int n,int k){
	if(n<0||k<0)return 0;
	if(k==0) return 1;
	if(cache[n][k] != -1) return cache[n][k];
	return cache[n][k] = solve(n,k-coin[n]) + solve(n-1,k);
	
}
int main() {
	int n,k,i;
	scanf("%d%d",&n,&k);
	for(i=0;i<n;i++){
		memset(cache[i],-1,sizeof(cache[i]));
		scanf("%d",&coin[i]);
	}
	printf("%d",solve(n-1,k));
}

물론 위는 2차원 배열을 사용해서 메모리 초과가 발생한다. 1차원 풀이는 아무리 생각해도 모르겠어서 여러 문서를 뒤져보고 이해했다.

2차원 배열을 사용하는 점화식이 $ dp[n][k] = dp[n][k-coin[n]] + dp[n-1][k] $인데, 여기서 n이 1증가하면 결국은 $ dp[n][k] = dp[n][k-coin[n]] $이되므로 $ \sum\limits_{i=coin[n]}^k cache[i] = cache[i] + cache[i - coin[n]] $이 된다.

#include <stdio.h>
int main(void) {
	int i,j,n,k,coin[100]={0},cache[10001]={0};
	scanf("%d%d",&n,&k);
	cache[0]=1;
	for(i=0;i<n;i++){
		scanf("%d",&coin[i]);
		for(j=coin[i];j<=k;j++)
			cache[j] += cache[j-coin[i]];
	}
	printf("%d",cache[k]);
	return 0;
}

문제

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

풀이

들어오는 이진수의 길이의 최대가 1000자리라고 했으니 십진수로 변환하면 최대 $2^{1001}-1$ 값이 들어온다는 의미이므로 long long을 이용하더라도 범위를 초과하므로 해결 할 수가 없다. 게다가 C언어에서는 직접 2진수 인풋을 받을 수 없으므로 문자열로 입력받아 처리하는게 제일 간편할것이다.

쉬프트 연산으로 17배는 $ x << 4 + x $ 이므로 똑같이 계산해주면 된다.

문자열이므로 가장 왼쪽(0번 인덱스)은 직접 계산을 하지않았는데 계산하지 않은 0번 인덱스는 항상 1~4 사이의 값이 나오므로 계산 후에 [0]의 문자가 무엇인지 보고 직접 출력하게 했다.

#include <iostream>
#include <string>
using namespace std;
int main() {
	int i=0,respos;
	string s,shifted,res,z="";
	cin>>s;
	res = shifted = s +"0000"; //왼쪽으로 << 4 연산;
	respos=res.size();
	for(i=s.size()-1;i>=0;i--){
		respos--;
		if(s[i]=='0')  continue;
		res[respos]++;
	}
	for(i=res.size()-1;i>0;i--){
		if(res[i]>='2'){
			res[i-1] += (res[i]-'0')/2;
			res[i] = ((res[i]-'0')%2)+'0';

		}
	}
	if(res[0]=='2') res[0]='0',cout<<"1";
	else if(res[0]=='3') res[0]='1',cout<<"1";
	else if(res[0]=='4') res[0]='0',cout<<"10";
	cout<<res;
}