백준 2168번: 타일 위의 대각선

Seungil Kim·2022년 2월 24일
0

PS

목록 보기
176/206

타일 위의 대각선

백준 2168번: 타일 위의 대각선

아이디어

대각선은 가로, 세로 모든 타일에 각 한 번씩 대응되고, 가로, 세로 길이의 최대공약수만큼 겹친다.
가로, 세로 길이가 서로소일 때 가로+세로-1이니까 gcd 단위로 쪼개고 이렇게 계산해도 됨. 근데 똑같음.

코드

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int x, y;
    cin >> x >> y;
    cout << x+y-gcd(x, y);

    return 0;
}

여담

수학이 싫어

profile
블로그 옮겼어용 https://ks1ksi.io/

0개의 댓글