반응형
알고리즘 사이트 알고스팟 에서 문제풀면서 알고리즘 공부를 하고있다.
이번에 푼 문제는 DRAWRECT라는 문제인데 튜토리얼 문제다.
문제 링크는 https://algospot.com/judge/problem/read/DRAWRECT
문제 내용은 직사각형 세개의 점 좌표가 주어졌을때 나머지 한 점의 좌표를 구하는것이다.
튜토리얼 문제라 그냥 쉽게 풀어버려야 하는데
코딩엔 문외한인지라 쉽지가 않았다.
x좌표 두쌍이 서로 같아야 하고 y좌표 두쌍이 같아야 한다는 점을 이용해야 하는데
막상 구현은 바로 못했다.
어떻게 구현할까 생각하다가 댓글에 누가 힌트를 적어놓은걸 보게 되었고
xor 연산을 이용하면 쉽게 구할 수 있다는걸 깨닫게 되었다.
xor 연산은 두 비트가 같으면 0 다르면 1을 반환하니까
a 와 b가 같으면 a^b는 0 다르면 0이 아닌 값이 될것이다.
xor을 이용하여 문제에 주어진 세 좌표의 x값과 y값들을 각각 xor 연산하면
마지막엔 결국 구하려는 좌표값이 계산된다.
저 그림을 예로 들면
x좌표일 경우
x1=x3 이므로
x1^x2^x3 = (x1^x3)^x2 = 0^x2
=x2=x4 가 된다
y좌표일 경우엔
y1=y2 이므로
y1^y2^y3 =(y1^y2)^y3 = 0^y3
=y3=y4 가 된다.
교환법칙이 성립하므로 순서에 관계없이
계산결과는 반드시 네번째 좌표가 나온다.
이런 간단한 문제도 수학이 들어가는걸 보면
수학이 정말 중요하다는 생각이 들었다
아래는 소스코드, c언어로 작성했다.
#include<stdio.h>
int main()
{
int n;
int i;
int x1,x2,x3;
int y1,y2,y3;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&x1);
scanf("%d",&y1);
scanf("%d",&x2);
scanf("%d",&y2);
scanf("%d",&x3);
scanf("%d",&y3);
printf("%d %d\n",x1^x2^x3,y1^y2^y3);
}
return 0;
}
반응형
