[C++] 백준 2725번: 보이는 점의 개수

 

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

최초풀이

시간초과 에러가 처음 발생하였습니다.

그래서 미리 모든 수를 구해 놓고 결과 값을 구하는 방식을 사용하였습니다.

#include <iostream>
#include <vector>

using namespace std;

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);
	int C;
	vector<int>v;
	cin >> C;
	v.push_back(0);

	int ans = 0;
	for (int i = 1; i <= 1000; i++) {
		for (int j = 1; j < i; j++) {
			if (gcd(i, j) == 1)
				ans++;
		}
		v.push_back(ans);
	}

	while (C--) {
		int N;
		cin >> N;
		cout << v[N] * 2 + 3 << '\n';
	}

	return 0;
}