알고리즘

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

Code Bomber 2020. 12. 21.

문제 링크 : programmers.co.kr/learn/courses/30/lessons/62048

 

코딩테스트 연습 - 멀쩡한 사각형

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을

programmers.co.kr

위 사진은 문제의 예시이다.

처음에는 규칙을 찾기 위해 고민을 했다.

그러다 똑같은 형태의 다각형이 반복된다는 것을 알아냈고 가로길이(W)와 세로길이(H)의 최대공약수만큼 반복 된다는 것을 알게 되었다.

 

그래서 다각형 한개를 기준으로 봤을때 몇개의 사각형이 포함되는지를 계산하고 거기에 최대공약수를 곱하면 되겠다고 생각했다.

 

위의 예시는 W = 8, H = 12이고 최대공약수(GCD)는 4이다.

 

반복되는 다각형의 가로길이는 (W/GCD = 8/4) 2이고 세로길이는 (H/GCD = 12/4) 3이다.

최대공약수로 나눈.. 즉, 반복되는 다각형 한개 기준으로 보면 각 다각형의 가로 길이와 세로길이의 최대공약수는 1이다.

이렇게 최대공약수가 1일 때는 가로길이 + 세로길이 - 1 만큼 선이 사각형을 지나간다.

그러므로 다음과 같은 식이 성립한다.

 

다각형 한개에서 제외되는 사각형의 수 = (W/GCD + H/GCD - 1) * GCD = W + H - GCD

 

그러므로 위의 예시는 8 * 12 - (8 + 12 - 4) = 96 - 16 = 80이 되는 것이다.

 

그래서 이 문제를 푸는 핵심 수식은

 

 W * H - (W + H - GCD)

 

이다.

 

using namespace std;

long long getGCD(long long a, long long b)
{
    if(a % b == 0) {
        return b; 
    }

    return getGCD(b, a%b);
}

long long solution(int w,int h) {
    long long W = w, H = h;

    // (w/g+h/g-1)g=w+h-g
    long long answer = W * H - (W + H - getGCD(W, H));
    
    return answer;
}

댓글