백준 2725번 보이는 점의 개수

< 백준 2725번 보이는 점의 개수 - 마포 코딩박 >

사용한 알고리즘: DP


 N이 주어졌을때 NxN 그래프 위의 점 중 원점에서 보이는 점의 개수를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 6~7)
 'dp[i]: ixi 크기의 정사각 좌표들 중 원점에서 보이는 점의 총 개수' 로 설정합니다.
 dp[i] = dp[i-1] + (추가로 보이는 수) 입니다.

(2) (코드 14~33)
 dp[1]~dp[1000] 을 구하는 함수를 만듭니다.
 (i-1)x(i-1) -> ixi 로 확장될 때 새로 생기는 선분은 정사각형의 윗변과 오른쪽변입니다.
 (추가로 보이는 수) = 2*(새로생기는 윗변에 추가로 보이는 수) = 2*((i,1)~(i,i) 중 추가로 보이는 수) 입니다.
 점 (x,y)가 보이는지 여부는 기울기로 판별합니다.
 (x,y) 가 보이는 점일 때 기울기 y/x 를 bool 배열로 기억하고, 이후는 보이지 않는다 생각합니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 1000;
	int C, N;
	// dp[x] = x번째 보이는 점들의 총 개수
	int dp[MAX+1];
	bool visited[MAX+1][MAX+1];
	int GCD(int x, int y){
	if(y==0) return x;
	return GCD(y,x%y);
	}
	// 기울기로 보이는 점 판별
	void MakeDP(int curr){
	if(curr>MAX) return;
	// 추가로 보이는 수 구하기
	int ADD = 0;
	// 반쪽만 구해서 2배 합니다.
	for(int i=1; i<curr; ++i){
	int x = i;
	int y = curr;
	// y/x = (y/g)/(x/g) 기약분수 만들기
	int g = GCD(y,x);
	x /= g;
	y /= g;
	if(visited[y][x]) continue;
	ADD++;
	visited[y][x] = true;
	}
	// curr번째 총 개수 = curr-1번째 총 개수 + 추가로 보이는 수
	dp[curr] = dp[curr-1]+2*ADD;
	MakeDP(curr+1);
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin>>C;
	dp[1] = 3;
	visited[1][1] = true;
	MakeDP(2);
	while(C--){
	cin >> N;
	cout << dp[N] << '\n';
	}
	return 0;
	}

view raw BOJ 2725.cpp hosted with ❤ by GitHub