문제

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