멀쩡한 사각형

Description

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

제한 사항

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

Example

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

Code

#include <bits/stdc++.h>
using namespace std;

long long solution(int w,int h) {
    long long answer = (long long)w * (long long)h;
    if (w == h){
        answer -= (long long)w;
    }
    else{
        // get Greatest Common Divisor
        int gcd = 1;
        for (int i = (w<h) ? w : h; i>0; i--){
            if(w%i == 0 && h%i == 0){
                gcd = i;
                break;
            }
        }
        answer -= (w/gcd + h/gcd -1)*gcd;
    }
    return answer;
}

Thoughts

처음에 보고 꽤 쉬워보이는 문제라고 생각했으나 은근히 오래 걸렸다. 문제에서 처음 중요한 부분이라 생각한 것은 data type의 범위이다.
주어진 w, h는 1억 이하의 자연수로 int 타입으로 주어졌지만, int*int를 하게 되면 int가 나오므로 문제의 결과 값에 맞게 (long long)으로 타입을 맞춰 줘야 하는 부분을 먼저 생각했다.

다음은 빼줘야할 정사각형의 갯수를 찾는 규칙을 발견하는 것이다.(이 문제의 전부)
처음에는 기울기로 접근하여 규칙을 찾아보려 했다.
기울기가 1일 때와 1이 아닐 때로 나눴고, 기울기가 1일 때 (w==h)일 때는 전체 사각형에서 한 변의 길이 수 만큼의 타일만 빼면 되고,
기울기가 1이 아닐 때는 전체 사각형의 갯수 - ceil(기울기) X min(w,h)라고 생각하고 제출 했더니 테스트 케이스 절반만 맞게 되어 다시 규칙을 찾아 보려 했다...

다음으로 찾은 규칙은 처음 직사각형에서 대각선을 그엇을 때, 같은 모양의 타일이 반복적으로 나오는 것을 확인하였고, 그 기준은 w, h의 최대 공약수 만큼의 갯수이다. 규칙적으로 나오는 타일에서는 잘라지는 부분이 가로 + 세로 - 1만큼 잘라져 나가기 때문에, 그 갯수에 최대공약수를 곱한 값을 전체 사각형 갯수에서 빼면 답이 나온다.