프로그래머스 - 점 찍기 [C++]

이 문제는 수학을 이용해서 푸는 문제이다. 일단 이 문제에서 주어지는 입력값 k, d 가 모두 [1, 1,000,000]  이므로 O(N) 이하 알고리즘을 고안해야 한다.

 

이 문제를 풀기 위해서 우선 1사분면에 반지름이 d인 원을 그려봤다.

a * k, b * k 에서 a와 b가 정수로 주어지기 때문에 점이 모눈종이에 규칙적으로 그려질 수 있다.

x^2 + y^2 = d^2 이기 때문에 y^2 = d^2 - x^2 이 되고, y = (d^2 - x^2)^(1/2) 가 된다. 이 값은 정수가 아닐 수 있으므로 double 로 계산하고, 이를 int로 캐스팅하면 정숫값이 나오게 된다.

이 정숫값을 k로 나누면 해당 x 값에서의 y가 d 이하인 y좌표의 개수가 나오고, 이를 반복문으로 돌려 계산하면 정답이 나온다.

 

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

using namespace std;

typedef long long ll;

double boundY(int x, int d) {
    ll squareX = (ll)x * (ll)x;
    ll squareD = (ll)d * (ll)d;
    
    ll squareY = squareD - squareX;
    
    return sqrt(squareY);
}

long long solution(int k, int d) {
    long long answer = 0;
    
    // (0, 0) 계산
    answer++;
    
    // 축 포함 점 미리 계산
    answer += (d / k) * 2;
    
    ll temp = 0;
    for (int i = k; i < d; i += k) {
        double dy = boundY(i, d);
        ll maxY = (ll)dy;
        temp += maxY / k;
    }
    
    answer += temp;
    
    return answer;
}