[프로그래머스] 두 원 사이의 정수 쌍 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/181187

 

문제 요약) 두 원의 사이의 정수인 좌표 개수를 출력하는 문제이다.

 

[풀이 1]

• 입력이 1,000,000 까지이기 때문에 완전 탐색으로 풀 수 없다.
• O(nlong(n))으로 풀릴 수 있기 때문에 하나의 x좌표에 대한 y의 최대 최소를 이분탐색으로 구하면 O(nlog(n))으로 문제가 해결된다.
• 하나의 사분면의 좌표만 구하면 나머지 3개도 같기 때문에 하나의 사분면의 좌표 개수를 구해준다.
• minY는 작은 원의 y좌표들보다 크거나 같은 최소 y 좌표이며, maxY는 큰 원의 y좌표들보다 작거나 같은 최대 y 좌표이다.

 

[풀이 2]  풀이 1을 고민하다 보니 굳이 복잡하게 풀 필요가 없었다.

• minY : x 좌표가 [1, r2] 일 때 r1^2 <= x^2 + y^2 를 만족해야한다.
  • 따라서 sqrt(r1^2 - x^2) 값의 올림값을 구하면 x가 k일 때 y의 최소 값을 구할 수 있다.
• maxY : minY와 같이 구하고 내림값을 구하면 된다.
• 작은원보다 x좌표가 더 큰 경우 큰원보다 작은 경우만 구하면 된다.

#include <string>
#include <vector>
#include <math.h>

using namespace std;

long long solution(int r1, int r2) {
	long long answer = 0;

	for (int i = 1; i <= r2; i++) {
		int minY = ceil(sqrt((long long)r1 * r1 - (long long)i * i));
		int maxY = floor(sqrt((long long)r2 * r2 - (long long)i * i));

		if (r1 < i)
			minY = 0;

		answer += (maxY - minY + 1);
	}

	return answer * 4;
}