[BOJ/C++] 2725: 보이는 점의 개수

🏅 Silver 1

✏️ 1차 솔루션

1. y 좌표/x 좌표 를 했을 때 기울기가 새로운 기울기라면 (0,0) 에서 보이는 좌표라고 판단
2. 기울기가 소수일 수 있기 때문에 set<double> s 에 기울기 저장하고 최종 set size 를 좌표 개수로 산정

🚨 1차 trouble

시간초과ㅠㅠ 틀렸다고 뜬다
double 형 set 를 선언했을 때, double 형으로 저장되지 않는 문제점 발생

✏️ 최종 솔루션

⭐️ 최대공약수를 구하기 위해 유클리드 호제법 사용
x 좌표, y 좌표의 최대공약수가 1이면 유일한 기울기이기 때문에 좌표 개수 count 가능
⭐️ n*n 사각형의 좌표 개수를 res[1001] 에 저장

1. 1*1 사각형일 때는 기울기 0(양의 방향), 1, 0(음의 방향) 3가지 이므로 res[1]=3
2. 2*2 사각형부터는
   (n-1)*(n-1) 사각형의 좌표 개수 + ( x 좌표가 n 이고 y 좌표가 n 보다 작은 경우 count 할 수 있는 좌표의 개수) * 2
   ❗️ 여기서 2를 곱해주는 이유는 y=x 축을 기점으로 대칭이기 때문에 그냥 한 쪽만 좌표 count 해주고 2 곱해주는 것

📌 self feedback

시간초과나 메모리 낭비가 심할 것 같은 연산은 미리 전체 범위에 대한 계산을 완료해서 저장해두고 실제로 입력 받은 값에 대해 출력만 해주는 형태로 풀어가도 나쁘지 않음

✏️ 최종 code

#include <iostream>
using namespace std;

int res[1001];

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    res[1]=3;
    for (int i=2; i<=1000; i++) {
        int cnt=0;
        for (int j=1; j<i; j++) {
            if (gcd(i,j)==1) cnt++;
            res[i]=res[i-1]+cnt*2;
        }
    }

    int c;
    cin >> c;
    while(c--) {
        int n;
        cin >> n;

        cout << res[n] << '\n';
    }
}