[백준] 16970번 : 정수 좌표의 개수 (C++)

16970번 : 정수 좌표의 개수

---

문제)

2차원 좌표 평면 위에서 두 점을 골라 선분을 그었을 때, 지나가는 점의 개수가 K개인 선분의 수를 구해보자.

가능한 점의 좌표 (x, y)는 0 ≤ x ≤ N, 0 ≤ y ≤ M 이고, x와 y는 정수이다. 선분의 양 끝점도 선분이 지나가는 점이다.

 

 

 

입력 :

첫째 줄에 N, M, K가 주어진다.

 

 

 

출력 :

첫째 줄에 지나가는 점의 개수가 K개인 선분의 수를 출력한다.

 

 

 

 

 

 

풀이)

// 16970. 정수 좌표의 개수
#include <iostream>
 
using namespace std;
 
int get_gcd(int a, int b)
{
    while (a % b != 0)
    {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return b;
}
 
int main()
{
    int n, m, _k;
    cin >> n >> m >> _k;
 
    int answer = 0;
    // 나올 수 있는 모든 점의 조합
    for (int i = 0; i < n + 1; i++)
    {
        for (int j = 0; j < m + 1; j++)
        {
            for (int k = 0; k < n + 1; k++)
            {
                for (int l = 0; l < m + 1; l++)
                {
                    // 완전히 동일한 점에 대한 처리
                    if (i == k && j == l) continue;
 
                    pair<int, int> x = make_pair(i, j);
                    pair<int, int> y = make_pair(k, l);
 
                    int cnt = 0;
 
                    // y 좌표가 같은 경우
                    if (i == k) cnt = abs(j - l) + 1;
                    
                    // x 좌표가 같은 경우
                    else if (j == l) cnt = abs(i - k) + 1;
                    
                    // x와 y가 일정하게 늘어나는 대각선에 있을 경우
                    // 예를 들면 (1, 1) -> (3, 3)
                    else if (abs(i - k) == abs(j - l))
                    {
                        cnt = abs(i - k) + 1;
                    }
 
                    else // 나머지 대각선으로 있는 경우
                    {
                        int _a = abs(i - k);
                        int _b = abs(j - l);
 
                        int gcd = get_gcd(_a, _b);
                        if (gcd == 1) cnt = 2;
                        else
                        {
                            if (_a > _b) swap(_a, _b);
                            cnt = (_b / (_b / gcd)) + 1;
                        }
                    }
 
                    if (cnt == _k)
                    {
                         answer++;
                    }
                }
            }
        }
    }
 
    // 양방향 간선이므로 / 2를 한다.
    cout << answer / 2;
 
    return 0;
}

 

 

---

출처 : https://www.acmicpc.net/problem/16970 

16970번: 정수 좌표의 개수