문제 출처

1. 문제설명

• 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있다.
• 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있다.
  • 모든 격자칸은 1cm x 1cm 크기이다.
• 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았다.
• 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태

• 사용할 수 있는 정사각형의 개수를 구하라

• 문제 분류
  • Implementation, Math, GCD

2. 알고리즘 설계

• 가로 길이, 세로 길이가 주어졌을 때,
• 이 길이의 최대공약수(GCD)만큼 패턴이 이어진다.
  • 내려가고-오른쪽-내려가고 가 반복된다.
• 예제 속 그림을 살펴보면 4개의 사각형으로 구성된 패턴이 반복되고 있다.
• 4개는 8과 12의 GCD이다.
• 그리하여 W/GCD + H/GCD - 1 == W + H - GCD가 된다.
  • -1은 가로로 가서 세로로 내려갈 때 시작점이 똑같기 때문에 중복을 제거해주는 것

3. 전체 코드

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

int gcd(int a, int b) {
    while(b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

long long solution(int w,int h) {
    LL ans = LL(w) * h;
    return ans - (w + h - gcd(w, h));
}

4. 소감

• solution 함수의 첫번째 줄에서 w에 long long을 씌운 걸 볼 수 있다.
• w, h가 int형 이기 때문에 곱셈의 결과도 int가 된다.
• 따라서 피연산자 중 하나에 강제 캐스팅을 하였다.