[프로그래머스] 멀쩡한 사각형

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

직선의 방정식을 구해서 직선보다 y좌표 값이 작은 사각형의 개수를 구하고 2배하는 방법으로 풀어보려했지만 시간초과가 계속 발생해서 결국 방법을 바꿔서 해결한 문제이다. 규칙을 찾는게 어려운 문제였다.

풀이

잘리는 사각형의 개수를 패턴을 통해서 알 수 있다.
w와 h의 최대공약수를 g라고 하면 가로가 w/g, 세로가 h/g인 패턴이 g번 반복되는 것을 알 수 있다. (아래 그림 참조)

그리고 해당 패턴 안에 잘리는 사각형을 생각해보면 w/g + h/g - 1개의 사각형이 잘린다는 것을 알 수 있다. 따라서 가능한 사각형의 총 개수는 w * h - g * (w/g + h/g - 1) 이므로 w * h - (w + h - 1)이 된다. 이 때 정답이 int 범위를 벗어나므로 주의해야한다.

코드

#include <algorithm>
using namespace std;

int gcd(int a, int b){
    if(a % b == 0) return b;
    return gcd(b, a%b);
}

long long solution(int w, int h)
{
    long long sum = (long long)w * (long long)h;
    if(w < h) swap(w, h);
    int g = gcd(w, h);    
    return sum - (w + h - g);
}