[BOJ 백준] 보이는 점의 개수(2725) C++

 

링크 : https://www.acmicpc.net/problem/2725

2725번: 보이는 점의 개수

 

문제 설명 : 

(0,0)에서 보이는 (x,y)의 개수를 구하려고 한다.(x,y >= 0, 정수)

(0,0)에서 (x,y)가 보이려면 (0,0)과 (x,y)를 연결하는 직선이 다른 점을 통과하지 않아야 한다. 예를 들어 (4,2)는 (0,0)에서 보이지 않는다. 그 이유는 (0,0)과 (4,2)를 연결하는 직선이 (2,1)을 통과하기 때문이다. 아래 그림은 0 <= x,y<=5인 경우에 (0,0)에서 보이는 점의 개수이다. 단, (0,0)은 계산하지 않는다.

N이 주어졌을 때, 원점에서 보이는 (x,y) 좌표의 개수를 출력하시오. (0 <= x,y <= N)

 

입력 : 

첫째 줄에 테스트 케이스의 개수 C(1<=C<=1,000)가 주어진다. 각 테스트 케이스는 자연수 N(1<=N<=1,000) 하나로 이루어져 있고, 한 줄에 하나씩 주어진다.

출력 : 

각 테스트 케이스에 대해 한 줄에 하나씩 (0,0)에서 보이는 점(x,y)의 개수를 출력한다.

 

예제 입력 : 

4
2
4
5
231

예제 출력 : 

5
13
21
32549

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 보이는 점의 개수
#if 1
#pragma warning(disable:4996)
#include <cstdio>

#define MAX (1000+3)

using namespace std;

int gcd(int a, int b) {
	// a > b가 되도록 swap(a,b)
	if (b > a) {
		int tmp = b;
		b = a;
		a = tmp;
	}

	// 유클리드 호제법
	int c;
	while (b) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

int C; // 테스트케이스 개수   
int N; // 인풋 숫자 - 범위

int cache[MAX];

int main() {

	// 0. 사전에 만들어놓기
	cache[1] = 3;
	int cnt = 0;
	for (int i = 2; i < MAX; i++) {
		cnt = 0;
		for (int j = 1; j < i; j++) {
			if (gcd(i, j) == 1) {
				cnt++;
			}
		}
		cache[i] = cache[i - 1] + (2 * cnt);
	}

	// 1. 입력
	//freopen("input.txt", "r", stdin);
	scanf("%d", &C);
	for (int i = 1; i <= C; i++) {
		scanf("%d", &N);
		printf("%d\n", cache[N]);
	}
	return 0;
}
#endif