오일러 프로젝트 85
균일한 격자 내에서 만들 수 있는 직사각형의 개수에 관한 문제이다. 눈금의 크기가 1인 격자에서 가로, 세로를 정했을 때 그 속에서 만들 수 있는 직사각형의 개수가 2백만개에 가장 근접할 때의 가로/세로를 구하는 것이다.
격자의 가로 크기를 x, 세로 크기를 y라 했을 때 그 내부에 존재하는 직사각형들의 가로 크기는 1, 2, 3, … x 이고 세로 크기도 1, 2, 3, … y 가 된다. 가로가 a 일 때 이 폭으로 x 에 들어갈 수 이는 경우는 (x + 1 – a) 개 만큼 있다. 세로의 경우에도 세로가 b라면 (x + 1 – b)개의 경우가 있을 수 있다. 따라서 a*b의 크기인 사각형은 x, y 내에 (x + 1 – a)*(y + 1 – b)개가 있을 수 있다.
가로 세로가 각각 x, y 인 경우 내부에 들어가는 모든 직사각형의 개수는 x, y 이하의 작은 양의 정수 a, b에 대해서 다음의 식으로 표현할 수 있다.
이 식을 풀면 
이를 적용해서 x, y 가 ‘적절한’ 값일 때 200만과의 차이가 최소가 되는 범위를 찾는다. 이 값들은 x, y가 각각 커질 때 마다 증가하게 된다. 참고로 x, y 가 각각 100일 때 이 값은 2,500백만 정도 되므로 x, y가 1…100 범위에 있는 경우를 가정해서 계산해보면 답을 구할 수 있다.
def nrects(x, y):
return (x * (x + 1) * y * (y + 1) // 4
def main():
limit = 2 * 10**6
ws = [(abs(nrects(x, y) -limit), x * y)
for x in range(1, 101) for y in range(1, 101)]
print(min(ws)[1])
main()
