코딩테스트 -- 두 원 사이의 정수 쌍- (프로그래머스 / C++)

프로그래머스

 

문제는 단순히 두 원 사이의 점의 갯수를 구하는 문제였습니다. 

조건도 아래 1개가 끝

1. 선위에 있는 점들은 포함

 

 

일단 시작은 두 원의 1/4만큼의 점의 갯수를 세어주고 *4하는 방식으로 시도해 보았습니다.

 

 

그렇게 만들어진 코드...

int BR=max(r1,r2);
    int SR=min(r1,r2);
    
    long long Bans=0;
    long long Sans=0;
    
    long long temp = 0;
    
    
    for(int i=0;i<BR;i++){// 1~BR-1까지의 점 구하기   // 큰원
        Bans+= sqrt(BR*BR-i*i)/1; // 그밑
        
    }
    
    for(int i=0;i<SR;i++){ // 작은원
        temp=SR*SR-i*i;
        if(fmod(sqrt(temp),1.0)==0){ // 맞아 떨어지는지
            
            Sans-=1;
        }
        Sans+= sqrt(temp)/1; // 그밑

    }
    

    answer=Bans-Sans;

 

단순하게 x축으로부터 올라가는 수선이 원에 닿는 y축좌표를 구해   그 좌표에서 x축까지의 점의 갯수를 계속 더해주고

작은 원의 점의갯수를 빼주었습니다. 

 

하지만 7~10번까지 테스트 케이스가 실패....

 

찾아보니 반지름의 크기가 1000000이 넘어가 제곱을 해주고 sqrt를 해줄시에 자료형이 변경변경되다보니 

오버플로우가 발생할 수 있다고 하네요..  (값이 약간 변경 될수도) 

 

 

그래서 방법을 바꿔보기로 했습니다.

 

한 x축에 대해서 

큰원안의 점들을

BR = (int)floor(sqrt(pow(r2, 2) - pow(i, 2))); // 큰원의 최대치   // 내림

작은원안의 점들을

SR = (int)ceil(sqrt(pow(r1, 2) - pow(i, 2))); // 작은원 최소치 / 올림

 

이런식으로 계산해서

 

 answer += (BR - SR + 1);
 
 .....
 
  return 4 * (answer + r2 - r1 + 1); /// 내부의 점들 + 축위의 점들

모든 점들을 계산해 주었습니다..

 

 

 

 

floor, ceil 을 사용할줄은 몰랐는데..... 원내부의 점 문제가 나오면 알아둬야겠네요...

 

 

 

 

 

 

 

ALL

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

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

    for (int i = 1; i < r2; ++i) {
        int BR = 0;
        int SR = 0;

        BR = (int)floor(sqrt(pow(r2, 2) - pow(i, 2))); // 큰원의 최대치   // 내림
        
        if(i < r1) {
            SR = (int)ceil(sqrt(pow(r1, 2) - pow(i, 2))); // 작은원 최소치 / 올림
        } 
        else {
            SR = 1;
        }
              
        answer += (BR - SR + 1);
    }

    return 4 * (answer + r2 - r1 + 1); /// 내부의 점들 + 축위의 점들
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!