프로그래머스 lv2 - 멀쩡한 사각형

✏️ 문제 풀이

< 직선의 방정식을 이용해보기 >

처음 이 문제를 봤을 때, 대각선에 대한 직선의 방정식을 만들고
격자의 좌표를 대입하여 교차 여부를 확인하는 방법을 생각해보았다.

그러나 쉽게 구현할 엄두를 내지 못했다.
주어진 W와 H 입력의 최대값이 1억 이하의 자연수였기 때문이다.
for(int i = 0; i < w; i++) 반복문을 x축과 y축을 고려해 2번 돌 생각을 하니 매우 큰 시간이 걸릴 것 같았다.
쿼드트리를 사용해볼까? 하는 고민도 해보았으나 쉽지 않았다.

이런 나의 접근법과 일치하는 방법으로 푼 사람이 있었다.
그 코드를 참고했다.

long long solution(int w, int h) {
    long long answer = 0;

    for (int i = 0; i < w; ++i) {
        answer += (int)((double)h*i/w);
    }

    return 2 * answer;
}

 

1) 주어진 격자의 크기 w와 h로 직선의 방정식을 만든다.

y = Gradient * x
Gradient = y좌표 간의 차 / x좌표 간의 차

(0, 0), (w, h)라고 할 때,
y = h/w * x 이다.

2) 교차 여부 판별 방법

직선의 방정식까지는 나도 쉽게 생각한 부분이었다.
내가 막힌 부분은 교차 여부를 어떻게 제한 시간(?) 내에 판별할 것인가 하는 부분이었다.

위의 코드는 반복문을 가로 또는 세로에 대해 한 번만 수행해도 된다.
원리는 다음과 같다.

1. 직선의 방정식에 x좌표를 대입해 y좌표를 구한다.
2. y좌표를 소수점 내림한다.
3. y좌표의 크기는 x좌표일 때, y좌표보다 아래에 있는 격자의 개수를 의미한다.

이 방법은 대각선 아래에 있는 격자만을 감지하지만, 대각선을 기반으로 양쪽이 서로 대칭이기 때문에
아래 영역에 대해 세어진 개수의 2배가 전체 직사각형의 격자 중 대각선과 교차하지 않는 격자의 개수가 된다.

< 직선의 특성 >

그런데 허탈할 정도로 더 쉽고! 간단한! 방법이 있다.
직선의 특성상을 이용한 것으로 대각선은 가로 W와 세로 H개의 격자를 지나간다는 점이다.

최대 1억번 반복문을 돌 필요없이 그냥... 두 정수를 더하면 된다.

단! W + H는 중복을 고려하지 않았다.
따라서 중복된 값을 빼주어야 한다.

중복된 격자의 개수는 W와 H의 최대 공약수이다.

대각선은 가로 W와 세로 H 만큼의 격자를 지나간다
따라서 대각선과 교차하는 격자의 개수는 W+H이다.

단 중복된 값(최대 공약수)을 제거해야 한다.

W + H - GCD(W, H)

< 유클리드 호제법으로 최대공약수 구하기 >

프로그래머스는 C++ Algorithm.h의 GCD 함수 사용을 지원하지 않는다.
따라서 이를 직접 구해주어야 했다.

최대공약수를 구하는 이론에는 대표적으로 유클리드 호제법이 있다.

https://velog.io/@e414/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EC%88%98%EB%A1%A0-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

방법은 간단하다.

1. 두 수를 나눈다.
2. 나머지가 0이 아니라면
3. 이전 연산의 몫을 이전 연산의 나머지로 나눈다.
4. 나머지가 0이 될 때까지 이를 반복한다.

처음 나머지 연산을 할 때, 둘 중 누가 더 큰 수인지 비교한 후 나눌 필요는 없다.
두 수의 크기는 결과에 전혀 영향을 주지 않는다.

직선의 특성을 이용해 구한 코드는 아래에 첨부하였다.

🖥️ 전체 코드

using namespace std;

typedef long long ll;

ll calcGCD(ll num1, ll num2){
    while(num2 != 0){
        ll temp = num2;
        num2 = num1%num2;
        num1 = temp;
    }
    return num1;
}
long long solution(int w,int h) {
    long long answer = 1;
    ll width = (ll) w;
    ll height = (ll) h;
    ll gcd;
    gcd = calcGCD(width, height);
    answer = width * height - (width + height - gcd);
    return answer;
}