[Level_2] 멀쩡한 사각형 (C++)

해당 문제는 로직을 이해를 해야한다. 

입출력에서 W = 8 이고 H = 12 로 주어진다고 가정하자. 

규칙을 한번 살펴 보자    

해당 그림과 같이 4번 반복하는 것이 보인다. 

수식화 해보면 W와 H의 최대공약수 만큼 반복된다. 8과 12의 최대공약수는 4이다. 

해당 값 뿐만 아니라 다른 값들도 최대 공약수 만큼 반복된다는 것을 임의의 숫자로 구해보면 알 것이다. 

 

반복되는 그림을 한번 살펴보자. 

너비가 2이고 높이는 3이다. 이 값들은 W와 H을 최대공약수로 나눈 값이라는 것을 알 수 있다. 

그리고 빈칸의 개수는 반복되는 그림의 "너비+높이-1" 인 것을 알 수 있다. 

 

그렇기 때문에 W와 H가 주어진다. 해당 값의 최대공약수는 반복되는 그림의 개수를 뜻하며 

각 그림에서의 빈칸의 사각형의 개수는 (너비+높이-1) 라는 것을 알 수 있다. 

 

따라서 사용할 수 있는 정사각형의 개수는 

 

W*H - (w+h-1)*(W,H의 최대공약수) 이다. 

 

using namespace std;
typedef long long ll;
long long solution(int w,int h) {    
    ll answer =1; 
    answer = (ll)w * (ll)h - (w+h);   
    int temp; 
    int w1, h1;     
    
    w1 = w; h1=h; 
    while(h1!=0){ //최대공약수
        temp = w1 % h1; 
        w1 = h1; 
        h1 = temp;         
    }    
    
    answer += w1; 
    return answer; 
}

 

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