[프로그래머스] 점 찍기 C++ 풀이 및 해설

https://school.programmers.co.kr/learn/courses/30/lessons/140107#qna

프로그래머스

풀이 방법

점 찍을 수 있는 x 좌표를 돌며

해당 x 좌표에서 찍을 수 있는 최대 y 좌표를 구한다.

최대 y좌표가 7이 나왔다고해서 0, 1, 2, ..., 7을 찍을 수 있는건 아니다.

k의 배수만 찍을 수 있으므로 최대 y 좌표에서 k로 나눈 몫만큼 찍을 수 있다.

단, 나누기에서 y좌표가 0인 경우는 포함되지 않으므로 나눌때마다 +1을 해주어야 한다.

 

x의 좌표는 0부터 k배수만 가능하므로 k를 더해가면 된다.

 

전체 코드

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

using namespace std;

long long solution(int k, int d) {
    long long answer = 0;
    
    for (long long x = 0; x <= d; x += k) {
        // d^2 = x^2 + y^2
        // y = sqrt(d^2-x^2)
        int maxY = sqrt((long long)d*d-(long long)x*x);
        answer += (maxY / k) + 1;
        // +1 이유 : y가 6일때 k는 2라면 6/2는 3이다.
        // (x, 2), (x, 4), (x, 6)에 (x, 0)을 추가했기에 +1을 해준것.
        
        // x는 0부터 k배수로 증가하여 d이하일때까지 반복.
        // 이때 구해지는 최대값 y에서 가능한 k배수의 개수를 구한다. (y/k)
        // 이때 0은 포함되지 않으므로 +1을 해준다.
    }

    
    return answer;
}