문제

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/HAMMINGCODE

풀이

단순한 구현문제. 입력이 7자리의 바이너리이므로 char로 받은뒤 int 배열에 넣고 xor을 사용해 syndrome 값을 구했다.

#include <stdio.h>
int main(void) {
	int t;
	scanf("%d",&t);
	while(t--){
		int i, syn = 0,encoded[8];
		char c;
		for(i=1;i<=7;i++){
			scanf(" %c",&c);
			encoded[i] = c-'0';
		}
		syn += ((encoded[1] ^ encoded[3]) ^ encoded[5]) ^ encoded[7];
		syn += 2 * (((encoded[2] ^ encoded[3]) ^ encoded[6]) ^ encoded[7]);
		syn += 4 * (((encoded[4] ^ encoded[5]) ^ encoded[6]) ^ encoded[7]);
		encoded[syn] ^= 1;
		printf("%d%d%d%d\n",encoded[3],encoded[5],encoded[6],encoded[7]);
		
	}
	return 0;
}

문제

풀이

이분 탐색 말고 다른 풀이 방법도 있을것 같은데 아 잘 모르겠다. 나는 멍청한가봐. 사실 이 풀이도 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;
}