반응형
유클리드호제법
-
[백준] 2168 터널 위의 대각선 with PythonPS 2022. 2. 21. 17:23
📌 BOJ 2168 터널 위의 대각선 💡 조건 한 변의 길이가 1cm인 정사각형 모양의 타일이 있다. 이 타일들을 가로가 xcm, 세로가 ycm인 직사각형 모양의 벽에 빈틈없이 붙였다. x와 y는 정수이다. 직사각형에 붙어 있는 x*y개의 타일 중에는 대각선이 그려진 타일도 있고, 그렇지 않은 타일도 있다. x*y개의 타일 중에서 대각선이 그려져 있는 타일의 개수를 구하는 문제. x와 y는 1,000,000,000 이하의 자연수 수학, 정수론, 유클리드 호제법유형의 문제 🖥 소스 코드 from sys import stdin from math import gcd x, y = map(int, stdin.readline().split()) print(x + y - gcd(x, y))🔖 예제 및 실행결과 예제 ..