[Algorithm] Programmers :: 멀쩡한 사각형

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

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

 

#include <algorithm>
using namespace std;
 
 
int gcd(long long a,long long b)
{
    long long maxNum = max(a,b);
    long long minNum = min(a,b);
    
    while(maxNum % minNum != 0)
    {
        long long temp = maxNum % minNum;
        maxNum = minNum;
        minNum = temp;
    }
    
    return minNum;
}
 
long long solution(int w, int h)
{
    long long answer = 1;
    long long a = w;
    long long b = h;
 
 
    answer = (long long)w + (long long)h - gcd(a,b); // w + h - (w와 h의 최대공약수) => 사라지는 사각형갯수.
 
    answer = (long long)w * (long long)h - answer;
 
    return answer;
}

이 문제는 패턴을 파악하는게 포인트인것같다. 한마디로 감이 좋아야한다. 약간의 수학쪽 센스가 섞인 문제를 풀어본 경험이 있으면, 그만큼 빨리 파악할 수 있는 문제같다.

알야할 방식?은 2가지다.

 

1. 잘려지는 작은구역의 범위는 너비는 w/gcd(w,h)이고, 높이는 h/gcd(w,h) 이다.

2. 이 작은구역의 블럭에서 대각선을 그으면 선이 지나는 네모의 개수는 작은구역의 w+h-1이다.