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

멀쩡한 사각형

문제 링크

멀쩡한 사각형

분석

가로 길이 W, 세로 길이 H인 사각형을 대각선으로 잘랐을 때, 1cm X 1cm의 정사각형 개수를 구하는 문제입니다.

전체 격자 개수는 W X H입니다.

대각선으로 가로지를 때, 작은 사각형이 최대공약수만큼 반복됩니다.
이때, 작은 사각형의 가로와 세로 길이는 최대공약수로 나눈 몫입니다.
즉, 가로 / gcd(W, H) + 세로 / gcd(W, H) - 1입니다.
가로 + 세로만큼 지나가는데, 반드시 한번은 한 정사각형의 꼭짓점에서 정확하게 지나가 가로와 세로 경계를 동시에 통과하기 때문에 - 1을 해주어야 합니다.

즉, W + H - gcd(W, H)개의 만큼의 정사각형이 대각선에 의해 잘려 사용할 수 없으며, W X H - (W + H - gcd(W, H))만큼 사용할 수 있습니다.

W, H의 값의 크기가 1억 이하의 자연수 이므로, long long 자료형을 사용해야합니다.

풀이

// 유클리드 호제법을 사용해 최대공약수를 구하는 방법
int gcd(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    
    return gcd(b, a % b);
}

long long solution(int w,int h) {
    long long answer = 1;
    
    // W X H - (W + H - gcd(W, H))로 정사각형 개수를 구합니다.
    // long long으로 오버플로우가 발생하지 않도록합니다.
    answer = static_cast<long long>(w) * static_cast<long long>(h) - (w + h - gcd(w, h));
    
    return answer;
}

성능 요약

시간 복잡도는 $O(log(min(w, h)))$입니다.

• gcd함수 $O(log(min(w, h)))$

공간 복잡도는 $O(log(min(w, h)))$입니다.

• gcd함수의 재귀 호출 스택 $O(log(min(w, h)))$

테스트 1 〉 통과 (0.01ms, 4.18MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.01ms, 4.14MB)
테스트 4 〉 통과 (0.01ms, 4.22MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 3.67MB)
테스트 7 〉 통과 (0.01ms, 4.21MB)
테스트 8 〉 통과 (0.01ms, 4.17MB)
테스트 9 〉 통과 (0.01ms, 4.21MB)
테스트 10 〉 통과 (0.01ms, 4.2MB)
테스트 11 〉 통과 (0.01ms, 4.14MB)
테스트 12 〉 통과 (0.01ms, 4.21MB)
테스트 13 〉 통과 (0.01ms, 4.15MB)
테스트 14 〉 통과 (0.01ms, 4.13MB)
테스트 15 〉 통과 (0.01ms, 4.17MB)
테스트 16 〉 통과 (0.01ms, 4.15MB)
테스트 17 〉 통과 (0.01ms, 3.66MB)
테스트 18 〉 통과 (0.01ms, 4.14MB)