멀쩡한 사각형 문제 설명 처음에 문제를 접했을 때, 아무리 생각해도 로직이 떠오르지 않았다. 그래서 조금 수학적으로 생각을 바꿔보았다. 대각선을 그릴 때에도 가로의 길이와 세로의 길이와 관련이 있다. 중복되는지점이 4개라는 것을 알 수 있다. 결국 이 대각선을 지나는 사각형의 개수를 구하기 위해서는 중복되는 지점의 개수를 찾아 빼주면된다. 이 경우에 중복되는 지점은 1개이다. 빨간 부분에서 중복되는 점이 발생한다. 결국 이 중복되는 점은 두 수(2,3)의 최대공약수이며 위 모양의 반복되므로 그 개수 *4를 해주면 중복되는 지점의 개수를 구할 수 있다. 결국에는 8과 12의 최대공약수가된다. 따라서 이 문제를 식으로 해결하면 answer = w*h(전체 사각형의 개수) - (w + h - gcd(w,h)가..
[Summer/Winter coding 2019] 멀쩡한 사각형 (cpp / python)
멀쩡한 사각형 문제 설명 처음에 문제를 접했을 때, 아무리 생각해도 로직이 떠오르지 않았다. 그래서 조금 수학적으로 생각을 바꿔보았다. 대각선을 그릴 때에도 가로의 길이와 세로의 길이와 관련이 있다. 중복되는지점이 4개라는 것을 알 수 있다. 결국 이 대각선을 지나는 사각형의 개수를 구하기 위해서는 중복되는 지점의 개수를 찾아 빼주면된다. 이 경우에 중복되는 지점은 1개이다. 빨간 부분에서 중복되는 점이 발생한다. 결국 이 중복되는 점은 두 수(2,3)의 최대공약수이며 위 모양의 반복되므로 그 개수 *4를 해주면 중복되는 지점의 개수를 구할 수 있다. 결국에는 8과 12의 최대공약수가된다. 따라서 이 문제를 식으로 해결하면 answer = w*h(전체 사각형의 개수) - (w + h - gcd(w,h)가..
2020.05.22