ACMICPC 2168 타일 위의 대각선
문제
한 변의 길이가 1cm인 정사각형 모양의 타일이 있다.
이 타일들을 가로가 xcm, 세로가 ycm인 직사각형 모양의 벽에 빈틈없이 붙였다. x와 y는 정수이다.
이 직사각형에 하나의 대각선을 그렸다.
직사각형에 붙어 있는 x*y개의 타일 중에는 대각선이 그려진 타일도 있고, 그렇지 않은 타일도 있다.
x*y개의 타일 중에서 대각선이 그려져 있는 타일의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 가로의 길이 xcm와 세로의 길이 ycm가 주어진다.
x와 y는 1,000,000,000 이하의 자연수이다. x와 y 사이에는 빈칸이 하나 이상 있다.
출력
첫째 줄에 대각선이 그려져 있는 타일의 개수를 출력한다.
골 때린다. 처음 낸 코드는 시간초과 나고(입력 최대값이 1,000,000,000)
어라..? 하면서 길을 잘못 든게
선을 그려야 하나..하면서 찾은 Bresenham 알고리즘
(http://forum.falinux.com/zbxe/?mid=graphic&page=3&document_srl=406146&listStyle=&cpage)
(문제풀이와는 전혀 상관 없지만 내용은 한번쯤 들을만 한 것 같다)
시간 초과를 낸 코드는 x일때의 y값과, x+1일 때의 y값의 차를 통해서 dx구간 동안 몇개의 상자를
지나갔나 x번 계산해주는 코드였고,
풀면서도 이러면 쉬울텐데...한 걸 구현해낸게 답이었다. 약간의 컨닝이 있었지만..
기울기 값 y/x * t (단, t는 현재 위치) 가 정수 일 때 타일의 모서리를 지나간다.
이 때 까지 지나간 타일 개수 세주면서 t 가 x 가 될 때까지 계산해주는 방식이다.
설명하기 어렵네...
에잇! 링크 투척!
고작해야 중등부 KMO 문제..
그래역시 알고리즘은 어렸을 때 접해야....ㅠㅠ
이참에 유클리드 호제법(Euclidean Algorithm)이나 완전히 기억하고 가야지.
2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b),
a와 b의 최대공약수는 b와 r의 최대공약수와 같다.