[Programmers] 두 원 사이의 정수 쌍

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/181187

프로그래머스

수학적인 사고능력이 필요한 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 원은 상하좌우 대칭이므로 (1 사분면 내 조건에 맞는 좌표들의 개수) * 4를 하면 정답이 나옵니다.

2. 따라서 [1, r2] 구간의 좌표들을 구하는데 이때 r1, r2, 그리고 x의 값이 연산 중 int 범위를 초과하며 오버플로우가 발생할 수 있으므로 x * 1LL * x와 같이 처리하여 int 범위를 초과하더라도 연산값이 잘 저장되도록 처리해 줍니다.

2.1 minY와 maxY는 피타고라스의 정리를 연상하면 쉽게 구할 수 있습니다.

3. 1번에서 설명했듯이 2번에서 구한 값에 4를 곱한 뒤 반환해 줍니다.

 

 

	#include <string>
	#include <vector>
	#include <cmath>
	using namespace std;
	long long solution(int r1, int r2) {
	long long answer = 0;
	for (int x = 1; x <= r2; x++)
	{
	long long maxY = floor(sqrt(r2 * 1LL * r2 - x * 1LL * x));
	long long minY = x >= r1 ? 0 : ceil(sqrt(r1 * 1LL * r1 - x * 1LL * x));
	answer += (maxY - minY + 1);
	}
	return answer * 4;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

지적, 조언, 질문 환영합니다! 질문 남겨주세요~