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

문제 URL

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

프로그래머스

 

[문제 설명]

가로의 길이 W와 세로의 길이 H가 주어질 때, 대각선이 그려진 사각형을 제외하고  사용할 수 있는 정사각형의 개수를 구하는 문제이다.

 

예시 그림

 

 

[문제 풀이]

정해진 규칙에 따라 구현하면 되는 문제였는데 그 규칙을 찾는 것이 쉽지 않았다. 

해당 문제에서 대각선에 의해 잘려나가는 사각형의 개수는 w+h-(두 수의 최대공약수)이다.

 

w, h에 따른 잘려나가는 사각형의 개수

 

 

[주의할 점]

입력이 최대 1억까지이기 때문에 long long형으로 바꿔주는 걸 잊지말아야 한다. 

---

using namespace std;

long long gcd(int num1, int num2) {  // 최대공약수를 구하는 함수
   long res;
   while (num2 != 0) {
      res = num1 % num2;
      num1 = num2;
      num2 = res;
   }
   return num1;
}
long long solution(int w,int h) {
    long long answer;
    long long temp = (w+h) - gcd(w,h);
    answer = (long long)w * (long long)h - temp;
    
    return answer;
}

 

참고: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=anyin93&logNo=221969084037