문제

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

풀이

문제를 요약하자면 시작점과 도착점의 좌표가 주어지고, 여러 원의 좌표와 반지름이 주어질때 시작점에서 도착점까지 도달하는데 최소로 원을 통과하는 횟수를 출력해야 하는 문제이다.

만약 임의의 원 C에 대해 시작점과 도착점이 둘다 안쪽에 있거나 바깥쪽에 있는 경우에는 해당 원을 거칠 필요가 없다는 뜻이므로 카운팅하지 않아도 된다. 즉, 시작점이 안쪽에 있고 도착점이 바깥쪽에 있거나 그 반대의 경우에만 카운팅을 해주면 최소 횟수를 구할수가 있는데 좌표 P가 C 내부에 있는지 이는 피타고라스의 정리를 사용하여 쉽게 판별할수있다.

우리는 시작점과 도착점이 서로 다를 경우에만 카운팅을 해주면 되므로 두 점을 판별한 결과값의 xor 연산 결과가 참일때만 카운트 해주면 된다.

#include <stdio.h>
int isInCircle(int x,int y, int Cx, int Cy, int Cr){
    return (x-Cx)*(x-Cx) +(y-Cy)*(y-Cy)<Cr*Cr;
}
int main(){
	int t,i;
	scanf("%d",&t);
	while(t--){
		int x1,y1,x2,y2,n,cx,cy,r,c=0;
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n);
		for(i=0;i<n;i++){
			scanf("%d%d%d",&cx,&cy,&r);
			c += isInCircle(x1,y1,cx,cy,r) ^ isInCircle(x2,y2,cx,cy,r);
		}
		printf("%d\n",c);
	}
}

문제

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