[프로그래머스] 멀쩡한 사각형 / C++

문제 설명

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

가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

 

제한 조건

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

 

입출력 예

W	H	result
8	12	80

 

 

코드

using namespace std;

int gcd(int a, int b) {
    int r;
    
    if (a < b)
    {   
        r = a;
        a = b;
        b = r;
    }
    while (b)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

long long solution(int w,int h) {
    long long answer;

    answer = ((long)w * (long)h) - (w + h - gcd(w, h));
    return answer;
}

 

문제 설명에 주어진 그림을 보고 동일한 패턴이 반복되는 것을 발견했다. 그래서 사각형의 가로와 세로를 최대공약수로 나누어 같은 비율을 가지는 작은 사각형으로 만들어 생각해보았다.

입출력 예에 주어진 가로 8, 세로 12인 사각형의 경우 최대공약수가 4이므로 가로 2, 세로 3인 사각형 크기의 패턴이 최대공약수인 4만큼 반복된다. 가로 2, 세로 3인 사각형의 한 꼭짓점에서 대각선에 위치하는 꼭짓점에 이르기 위해서는 가로로 2만큼 이동하고 세로로 3만큼 이동해야 한다. 이때, 시작 지점이 동일하므로 1만큼 빼주면 멀쩡하지 않은 사각형 즉, 두 꼭짓점을 잇는 대각선이 지나가는 사각형의 개수가 된다.

전체 사각형에서는 이러한 패턴이 4번 나타나므로 가로 8, 세로 12인 사각형에서 멀쩡하지 않은 사각형은 ((2 + 3 - 1) X 4) 개이고, 4를 각 항에 곱하여 (8 X 12 - 4)로 나타낼 수 있다. 따라서 다음 식을 통해 답을 구할 수 있다.

(멀쩡한 사각형의 개수) = (전체 사각형의 개수) - (멀쩡하지 않은 사각형의 개수)
(멀쩡한 사각형의 개수) = ((가로) X (세로)) - ((가로) + (세로) - (가로와 세로의 최대공약수))

 

링크

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

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

github.com/inbdni/Programmers/blob/master/level02/%EB%A9%80%EC%A9%A1%ED%95%9C%EC%82%AC%EA%B0%81%ED%98%95.cpp

inbdni/Programmers