📒활용개념

이 문제는 어떤 개념이나 알고리즘이 필요한 문제는 아니다. 다만 문제에서 주어진 범위의 수를 활용하면 int 범위를 넘어갈 수 있기 때문에 long long int를 사용하는 것이 안전하다.

📌문제설명

Ax + By + C = 0 으로 표현되는 n개의 직선에 대하여, 이 직선들의 교점 중 정수 좌표에 별()을 그린다.
이 별을 문자열로 나타낼 때 격자판의 크기는 별을 포함하는 최소한의 크기만 나타낸다.
(별은 로 나타내고 나머지는 .으로 나타낸다.)

📌구현

1. AD - BC = mod가 0인지 아닌지 검사
2. 정점이 자연수가 되는지를 확인한다.
3. 정점이 자연수라면 vector< pair< long long, long long>> 에 저장
4. 출력해야 하는 map을 .으로 초기화한 후 정점 부분만 *으로 변경

#include <iostream> 
#include <string> 
#include <vector> 
#include <algorithm> 
#include <climits> 
using namespace std; 
vector<string> solution(vector<vector<int>> line) { 
	//map의 크기를 정하는 최소와 최대값
    long long minX = LLONG_MAX, minY = LLONG_MAX; 
    long long maxX = LLONG_MIN, maxY = LLONG_MIN;
    //정수 정점을 저장한다.
    vector<pair<long long, long long>> coords; 
    int lineSize = line.size(); 
    for (int i = 0; i < lineSize; i++) { 
        for (int j = i + 1; j < lineSize; j++) { 
        	//자신을 제외한 직선과 정점 검사
            long long A = line[i][0], B = line[i][1], E = line[i][2]; 
            long long C = line[j][0], D = line[j][1], F = line[j][2]; 
            long long xNumerator = B * F * 1LL - E * D * 1LL; 
            long long yNumerator = E * C * 1LL - A * F * 1LL; 
            long long mod = A * D * 1LL - B * C * 1LL;
            //1번 조건 검사
            if (mod == 0) { continue; } 
            //2번 조건 검사
            if (xNumerator % mod || yNumerator % mod) { continue; } 
            
            long long x = xNumerator / mod; 
            long long y = yNumerator / mod; 
            minX = min(minX, x); 
            minY = min(minY, y); 
            maxX = max(maxX, x); 
            maxY = max(maxY, y);
            //3번 조건 실행
            coords.push_back({ x, y });
        } 
    } 
    //answer 초기화
    string row = string(maxX - minX + 1, '.'); 
    vector<string> answer(maxY - minY + 1, row);
    
    //필요 부분만 *로 초기화+coord에 저장된 변수 모두 방문
    for (pair<long long, long long> coord : coords) { 
        answer[maxY - coord.second][coord.first - minX] = '*';
    } 
    return answer; 
}

📌주의점

• 수학적인 접근이 중요하다.
• 문제를 어떤 순서로 풀지 생각을 해야한다.
• 문제의 조건을 이해해야한다.