yoo.dev

유클리드 호제법이란 최대공약수를 구하기 위해서는 유클리드 호제법을 사용하면 된다. 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 뜻한다. 먼저 1071을 1029로 나눈다. 42라는 나머지가 나온다. 만약 1029가 42로 나누어진다면 1071 = 42 * n이 될텐데 42로 안나눠지니까 42는 최대공약수가 될 수 없다. 그 후 1029을 42로 나눠서 21을 얻는다. 이때 42는 21로 나누어지기 때문에 21을 약수로 가진다. 따라서 최대공약수는 21이다. 글로 읽으면 복잡한데 결국 1071은 1071 = (1029 * 1) + 42 = ((42 * k) * 1) + 42 = (((21*2) *k) *1) + (21*2) = 21 * (k+2) 로 쓰일수 있다는걸 생각..

문제 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3≤N≤100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수 www.acmicpc.net 풀이 같은 간격으로 가로수를 심기 위해서 각 간격들의 최대공약수를 구해줬다. 두 가로수 사이에 심을 가로수의 개수는 간격 // 최대공약수 -1 이다. import sys from math import gcd # 이미 심어져 있는 가로수 수 N = int(sys.stdin.readline()) # 첫 가로수 위치 a = int(sys.stdin.readline()) # 가로수들 사이의 값을 저장할 배열 arr = [] # 가로수들 사이의 간격 저장 for..