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

문제

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

프로그래머스

큰 원 - 작은 원 을 하는 문제였다.

 

문제 풀이

처음에는 4분의 1 범위에 대해서 완전탐색을 했고, 시간 초과가 났다. 항상 문제를 풀 때 시간복잡도가 어떤 방법으로 풀어야 할지 생각을 좀 해야겠다. 사실 이번에도 안될거 알면서 완전탐색으로 해본거라... 안될 것 같으면 다른 방법을 찾자!! 코테는 제한 시간이 정해져 있으니까!

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

using namespace std;

double distance(int x, int y){ //0,0부터 x,y까지의 거리
    double dist = sqrt(x*x + y*y);
    return dist;
}

long long solution(int r1, int r2) {
    long long answer = 0;
    int i,j;
    int count=0;
    
    for(i=1;i<=r2;i++){
        for(j=0;j<=r2;j++){
            double dist = distance(i,j);
            if(dist <=r2 && dist >=r1){
                count++;
            }
        }
    }
    
    answer = count*4;
    return answer;
}

 

 

이중포문을 돌리지 않고 한 번의 포문으로만 계산할 수 있는 방법인 각 i에 대해 y축 점의 개수 구하기로 해결했다.

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

using namespace std;

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

    for(int i=1;i<r2;i++){
        //큰 원(내림) - 작은 원(올림)이 세로축 점의 개수
        //x^2 + y^2 = a^ -> y = sqrt(pow(a,2) - pow(x, 2))
        // y값 = sqrt(pow(r2,2) - pow(i,2));
        
        big = (int)floor(sqrt(pow(r2,2)-pow(i,2)));
        if(i<r1){
            small = (int)ceil(sqrt(pow(r1,2)-pow(i,2)));
        }
        else{
            small = 1; //j가 0일 경우는 빼고 계산해야 함
        }        
        answer += big - small + 1;        
    }
    
    answer += (r2-r1+1);
    answer *=4;
    
    return answer;
}