프로그래머스 멀쩡한 사각형 c++ (유클리드 호제)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/62048

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

문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한사항

• W, H : 1억 이하의 자연수

입출력 예

입출력 예 설명

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

풀이

'프로그래머스 / Summer/Winter Coding(2019) / 멀쩡한 사각형'으로 분류되어 있는 문제이다.

 

글에 사용한 알고리즘을 '유클리드 호제'라고 적어놨는데, 이는 최대공약수를 구하는 알고리즘 기법이다.

유클리드 호제법이란,

두 수 a>b가 있을 때 a를 b로 나눈 나머지 값 c =a%b;을 구하고,

b를 c로 나눈 나머지 c2 = b%c;를 구하는 과정을 반복하여 나머지가 0이 되었을 때

나누는 수가 a와 b의 최대공약수이다.

 

그럼 이 문제에 어디서 최대공약수를 이용할까?

 

w=1, h=1  :   1*1-1 ==0;

w=1, h=2 :  1*2-(1+2-1) ==0;

w=1, h=3 : 1*3-(1+3-1) ==0;

 

w=2, h=2 : 2*2-2 == 2;

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

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

 

w=3, h=3 : 3*3-3 == 3;

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

w=3, h=5 : 3*5-(3+5-1) == 8;

w=3, h=9 : 3*9-(3+9-3) == 18;

 

w=8, h=12; 8*12-(8+12-4) == 80;

 

즉 w==h일 땐, 대각선에 의해 삭제되는 정사각형은 w or h 개;

w!=h일 땐, 대각선에 의해 삭제되는 정사각형은 w+h에서 w,h의 최대공약수를 뺀 만큼이다.

 

이에 따른 점화식은,

w==h : w*h-w;

w!=h : w*h-(w+h-gcd(w,h));

이다.

w*h값은 int의 범위를 넘어갈 수 있는 것에 유의하자.

코드

using namespace std;

int gcd(int l,int h){
        if(h%l==0)
            return l;
        else
            return gcd(h%l,l);
}

long long solution(int w,int h) {
    int least;
    long long answer;
    long long ww=w, hh=h;
    if(w==h)
        return ww*hh-ww;
    else if(ww<hh)
       answer  = ww*hh - (ww+hh-gcd(ww,hh));
    else
       answer = ww*hh - (ww+hh-gcd(hh,ww));

    return answer;
}