[프로그래머스] 181187: 두 원 사이의 정수 쌍

Happy New Year!

 

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

프로그래머스

 

수학 문제는 로직 구현시 기존 존재하는 공식이나 정리가 있는지 확인하고, 이를 사용하는 것이 중요하다.

 

원 공식 : x2+y2=r2 을 이용하여 x 지점에 대해 두 원 사이에 속하는 y 점 개수를 구하면 된다.

원이므로 대칭을 이용하여, 4사분면의 한 부분만 구하고, 구한 개수 *4 를 하여 답을 구한다.

 

로직

1) x 위치를 기준으로 1~r2 까지 반복문을 돌면서

- x가 작은 원(r1)보다 작을 경우 큰 원에 속한 가장 큰 y점(maxY)과 작은 원에 속하지 않은 가장 작은 y점(minY) 사이의 점 개수를 구한다.

- x가 r1 이상일 경우 작은 원에 의해 가려지는 점(r1에 속한 점)이 없으므로 큰 원에 속한 가장 큰 y점까지 개수를 더한다.

 

2) y축에 있는 점의 개수를 더한다. (대칭이므로 y축 or x축 중 한 축 위의 점들만 구한다.)

 

코드

#include <bits/stdc++.h>
int maxY, minY;
using namespace std;

long long solution(int r1, int r2) {
    long long answer = 0;
    // 1. r1, r2 원 안의 점 구하기
    for (int r=1;r<r2;r++){
        maxY = floor(sqrt(pow(r2,2) - pow(r, 2)));
        minY = ceil(sqrt(pow(r1,2) - pow(r, 2)));
        if (r<r1){
            answer += (maxY-minY)+1;
        }
        else answer += maxY;
    }
    // 2. y축 점 구하기
    answer += (r2 - r1) + 1;
    // 3. 사분면 고려
    answer *= 4;
    return answer;
}