[BOJ][C++] 백준 2168번: 타일 위의 대각선

https://www.acmicpc.net/problem/2168

2168번: 타일 위의 대각선

 

문제

한 변의 길이가 1cm인 정사각형 모양의 타일이 있다. 이 타일들을 가로가 xcm, 세로가 ycm인 직사각형 모양의 벽에 빈틈없이 붙였다. x와 y는 정수이다.

이 직사각형에 하나의 대각선을 그렸다. 직사각형에 붙어 있는 x*y개의 타일 중에는 대각선이 그려진 타일도 있고, 그렇지 않은 타일도 있다. x*y개의 타일 중에서 대각선이 그려져 있는 타일의 개수를 구하는 프로그램을 작성하시오.

 

풀이

구현은 쉽지만 발상이 어려운 문제

입력 받은 두 값을 합하고 두 수의 최대공약수를 빼주면 된다.

 

#include <iostream>

using namespace std;

int gcd(int a, int b) {
    if(b==0) {
        return a;
    }
    return gcd(b, a%b);
}

int main() {
    int r,c;
    cin >> r >> c;
    int g = r>c ? gcd(r,c) : gcd(c,r);
    cout << r+c-g;
    return 0;
}

 

증명은 이 블로그가 너무 잘 설명해주었기 때문에 생략!

[백준 2168번] 타일 위의 대각선