[Summer/Winter coding 2019] 멀쩡한 사각형 (cpp / python)

멀쩡한 사각형

문제 설명

처음에 문제를 접했을 때, 아무리 생각해도 로직이 떠오르지 않았다. 그래서 조금 수학적으로 생각을 바꿔보았다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

대각선을 그릴 때에도 가로의 길이와 세로의 길이와 관련이 있다. 중복되는지점이 4개라는 것을 알 수 있다.

결국 이 대각선을 지나는 사각형의 개수를 구하기 위해서는 중복되는 지점의 개수를 찾아 빼주면된다.

이 경우에 중복되는 지점은 1개이다.

빨간 부분에서 중복되는 점이 발생한다.

결국 이 중복되는 점은 두 수(2,3)의 최대공약수이며 위 모양의 반복되므로 그 개수 *4를 해주면 중복되는 지점의 개수를 구할 수 있다.

결국에는 8과 12의 최대공약수가된다.

따라서 이 문제를 식으로 해결하면 answer = w*h(전체 사각형의 개수) - (w + h - gcd(w,h)가 된다.

 

 

 

문제 풀이

소스코드 : C++

#include <iostream>
#define ll long long
using namespace std;

ll GCD(ll a, ll b){return a%b==0?b:GCD(b,a%b);}
ll solution(int w,int h) {
    return w*h - (w + h -GCD(w,h));
}

c++이나 자바와 같은 언어들은 변수들의 크기가 정해져있다 (int, long 등) 따라서 계산할 때 생기는 오버플로우도 생각해줘야하는데 위와 같이 제출을하게 된다면 답이 틀리게 나온다.

왜냐하면 w와 h가 int형인 상태에서 연산을 진행하게 되면 연산을 먼저 수행 후 long long값으로 캐스팅하여 저장하기 때문에 연산하는과정에서 int형을 벗어나는 경우가 생길 수 있다.

따라서 아래와 같이 먼저 long long으로 캐스팅 후 문제를 해결해야 한다.

#include <iostream>
#define ll long long
using namespace std;

ll GCD(ll a, ll b){return a%b==0?b:GCD(b,a%b);}
ll solution(int w,int h) {
   ll answer = (ll)w * (ll)h;
    return answer - (w + h -GCD(w,h));
}

 

소스코드 : Python

자료형의 크기는 상관 안해도 되는 파이썬...

def solution(w,h):
    get_GCD = lambda a, b : b if a%b==0 else get_GCD(b,a%b)
    GCD = get_GCD(w,h)
    return w*h - (w + h - GCD)