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

 

Level. 2

 

 

문제

 

 

x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다.
반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.
* 각 원 위의 점도 포함하여 셉니다.

* 제한 사항
- 1 ≤ r1 < r2 ≤ 1,000,000

 

풀이

#include <string>
#include <vector>
#include <cmath>
#include <iostream>

using namespace std;

// x^2 + y^2 = r^2

long long solution(int r1, int r2) {
    
    long long answer = (r2-r1+1)*4 ; // x 또는 y좌표가 0 일때 
    for(int i=1; i<r2; i++){
        long long max = floor(sqrt((long long)r2*r2 - (long long)i*i));
        long long small = ceil(sqrt((long long)r1*r1 - (long long)i*i)); // 무조건 포함되기위해 반올림
        if(i>=r1) small = 1; 
        answer += (max-small+1)*4;

    }

    return answer;
}

 

해결방법

1. x좌표 또는 y좌표가 0일 때의 격자점 개수를 먼저 구한다.

2. (x^2 + y^2 = r^2) 공식을 활용해 x좌표를 1씩 더해가며 y좌표를 구하고, 이를 이용해 격자점의 갯수를 구한다. 

     큰 원의 y좌표의 내림한 값(max), 작은 원의 y좌표의 반올림 한 값(small)을 통해 x좌표당 격자점의 갯수를 구한다. 
     이때 제1 사분면의 격자점의 개수만을 구한 후 4를 곱해준다.   

     (max-small+1)*4

3. x좌표가 작은 원의 반지름보다 커지면, 큰 원의 격자점 갯수만 구한다. 

 

---

다른 풀이

#include <string>
#include <vector>
#include <cmath>
using namespace std;

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

    for (int t = 1; t <= r2; ++t)
    {
        int h2 = floor(sqrt(pow(r2,2)-pow(t,2)));        
        int h1 = (t < r1)?ceil(sqrt(pow(r1,2)-pow(t,2))):0;        
        answer += h2-h1 + 1;        
    }
    return 4*answer;
}

 

---

https://school.programmers.co.kr/learn/courses/30/lessons/181187?language=cpp

프로그래머스