C++ [Algorithm] - Swea 16910 원 안의 점(D3)

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AYcllbDqUVgDFASR&categoryId=AYcllbDqUVgDFASR&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=2

SW Expert Academy

---

문제 요약

x^2+y^2<=N^2인 격자점의 개수를 구하는 프로그램을 작성

격자 점의 개수를 구하라고 하니 무조건 정수의 값만 구하면 된다.

 

예를 들어 N값이 2로 들어왔을 때 반지름이 2인 원이 생성된다고 생각하자.

그러면 반지름이 2인 원에 정수값으로 x^2+y^2<=N^2 이 공식이 성립되는 좌표 값은

X	Y
0	0
1	1
2	0
0	1
0	2
-1	1
-2	0
-1	-1
0	-1
0	-2
1	-1
1	0
-1	0

그림이 좀 무섭네;;

 

이런 식의 13개의 좌표 값이 나올 것이다.

우선 2중 반복문으로 x^2+y^2<=N^2이 공식이 성립되면 count 값을 증가시키는 반복문을 만들어 보자

 

		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= N; j++) {
				if ((i * i) + (j * j) <= N * N) {
					cnt++;
				}
			}
		}

 

이렇게 만들면 (0,0), (1,0), (2,0), (1,1), (0,1), (0,2) 좌표값인 총 cnt가 6개가 될 것이다.

 

우리는 1사분면의 개수만 구했다. 이제 총 4사분면에 해당하는 값을 구해줘야 한다.

 

1. 4사분면의 개수를 구하기 위해 4*cnt를 해준다.

2. 4사분면의 개수를 구했기 때문에 (0,0)은 4개가 중복된다 따라서 -3을 해준다.

3. 원의 경계 선분에 위치한 좌표는 중복해서 세어진다. 따라서 N만큼의 좌표가 원의 경계선에 존재하므로 4*N 값을 빼준다.

---

코드

#include<iostream>

using namespace std;

int main(int argc, char** argv)
{
	int test_case;
	int T;
	int N;
	int cnt = 0;
	
	cin >> T;
	
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N;
		cnt = 0;

		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= N; j++) {
				if ((i * i) + (j * j) <= N * N) {
					cnt++;
				}
			}
		}
		cout << "#" << test_case << " " << 4 * cnt - 3 - 4 * N << endl;
	}
	return 0;
}