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

programmers.co.kr/learn/courses/30/lessons/62048

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

 

풀이

가로가 w, 세로가 h인 직사각형을 대각선으로 자를 때 사용할 수 없게 되는 사각형의 개수가 몇개가 나오는지 규칙을 파악 해야한다. 항상 이러한 규칙을 파악할 때는 작은 단위로 분할하는 것이 좋은 것 같다. 또한 각각의 입력값의 크기가 클때, long long으로 변수를 복사하고 하는게 좋은 것 같다.

 

w=1, h=1 : (1+1)-1=1 

w=2, h=2 : (2+2)-2=2

w=3, h=3 : (3+3)-3=3

 

w=1, h=2 : (1+2)-1=2

w=2, h=3 : (2+3)-1=4

w=3, h=4 : (3+4)-1=6

 

w=2, h=4 : (2+4)-2=4

w=2, h=5 : (2+5)-1=5

w=2, h=6 : (2+6)-2=6

 

위와 같이 대각선으로 자를 때 사용할 수 없게 되는 사각형의 개수는 가로 +세로 - 최대 공약수의 개수를 가진다.

가로와 세로의 최대 공약수는 유클리드 알고리즘을 이용하면 쉽게 구할 수 있다.

 

전체 코드

#include <algorithm>
using namespace std;
typedef long long ll;

ll getGcd(ll a, ll b) {
    if(a < b) swap(a, b);
    while(1) {
        if(a % b == 0) return b;
        ll tmp = b;
        b = a;
        a = tmp % a;
    }
}

ll solution(int w, int h) {
    ll answer = 1, lw = w, lh = h;
    
    return (lw * lh) - (lw + lh - getGcd(lw, lh));
}