목록백준 2168 (1)

시작이 반

[백준] 2168번 (python 파이썬)

사실 유클리드 호제법에 관련된 문제이다. 위의 그림을 보고 알 수 있는것은 1. 대각선이 꼭지점을 지나가지 않는 직사각형은 x + y -1 대각선이 꼭지점을 지나가는 직사각형은 x + y -1 - (점의 개수) 이다. 2. 점의 개수는 어떻게 구하냐 x, y의 최대공약수 - 1이다 즉 점이 없는 직사각형들은 (x, y의 최대공약수 - 1) 을하면 0이 나오기 때문에 이도 성립한다 1, 2를 종합해보면 x + y - gcd(x, y) 라는 식을 구할 수 있다. x, y = map(int, input().split(' ')) def gcd(a, b): if b > a: a, b = b, a while True: if b == 0: break a, b = b, a % b return a print(x + y ..
알고리즘/백준 2021. 3. 15. 20:51
이전 Prev 1 Next 다음