프로그래머스 - 점 찍기 (C++)

 

 

이렇게, 좌표평면에서 d보다 가까운 거리에 있는 점들의 개수를 출하면 된다.

모든 점을 다 세는 것은 아니고,x와 y가 2의 k의 배수인 경우만 세주면 된다.

 

 

 

문제 풀이

---

 

 

임의의 좌표 (a, b)를 보자.

(a,b)가 주황색 원 위의 점이라고 가정해보겠다.

 

a 좌표에 대해, 위쪽으로 점을 찍을 때, 점의 최대 y좌표는 b와 같다.

 

왜냐하면, 원점으로부터 거리가 d를 초과하는 좌표엔 점을 찍을 수 없다.

원의 성질을 생각했을 때, 원점으로부터 (a,b)까지의 거리가 정확히 d가 된다.

그렇기 때문에, x가 a일 때 y값이 b를 초과하게 되면 원점으로부터의 거리는 d를 초과하게 된다.

 

그렇다면, a와 b의 값을 안다면 x가 a일 때 위쪽에 점을 몇 개 찍을 수 있을지 계산할 수 있을 것이다.

예를 들어 b가 6.5라고 가정한다면 위 그림처럼 x가 a일 때 위쪽으로 6개의 점을 찍을 수 있을 것이다.

 

b는 어떻게 구할 수 있을까?

간단하게 피타고라스의 정리를 이용해서 구할 수 있다.

 

 

좌표평면에 위와 같은 빨간 삼각형을 그려볼 수 있다.

이 삼각형의 밑변의 길이는 a이고, 빗변의 길이는 d이다.

 

피타고라스의 정리를 이용하면, b^2 = d^2 - a^2 이다.

a와 d를 안다면, b를 쉽게 구할 수 있다.

 

a는 x좌표의 값이기 때문에

반복문을 통해 0~d까지 이동하며 위에 찍을 수 있는 점의 수를 계산한 뒤 모두 더하면 답을 도출할 수 있다.

 

하지만, 문제에는 조건이 하나 더 있다.

x와 y는 반드시 k의 배수여야 한다는 것이다.

 

이를 해결하는 방법은 간단하다.

 

먼저, x는 반복문에서 움직일 때 1씩 움직이는 것이 아니라 k씩 움직이면 된다.

어차피, x가 k의 배수가 아니면 점을 찍지 못하기 때문에 k씩 더해가며 해당 좌표에서만 점의 개수를 구하면 된다.

 

y에 대해서는 어떻게 해결할까?

 

k를 고려하지 않았을 때, 위에 찍을 수 있던 점의 개수를 k로 나누어 준 뒤 1을 더하면 된다.

k가 4이고, 위에 찍을 수 있는 점이 10개라고 가정해보자.

이 때, 10을 4로 나누면 몫은 2가 나온다. y값이 4일때, 8일 때 찍을 수 있는 것이다.

 

하지만, 이 문제의 경우 y값이 0인 경우에도 점을 찍을 수 있다.

그렇기 때문에 1을 꼭 더해주어야 한다.

 

 

 

풀이 코드

---

 

int Interval = k;
int Distance = d;

 

먼저 가독성을 위해, 변수의 이름을 새로 정의하였다.

 

long long DotCount = 0;
for (int i = 0; i <= Distance; i += Interval)
{
    long long SqrtValue = sqrt(pow(Distance, 2) - pow(i, 2)) / k;
    SqrtValue++;

    DotCount += SqrtValue;
}

return DotCount;

 

이후, 위에서 말한것 그대로 코드로 구현하면 된다.

 

i는 0부터 Distance까지 이동하며 점의 개수를 셀것이다.

다만, i가 Interval의 배수라는 조건이 있기 때문에 i를 1씩 증가시키는게 아니라 Interval씩 증가시켰다.

 

이후, 피타고라스의 정리를 이용하여, 위로 찍을 수 있는 점의 최대 개수를 구한 뒤 이를 k로 나눠주었다.

그 다음 1을 더해줌으로서 y좌표가 0인 점도 함께 세주었다.

 

그렇게 나온 값을  DotCount에 지속적으로 더해주면 끝이다.

 

 

이 문제는 알고리즘에 관한 문제라기보단 완전한 수학문제이다.

이런 유형의 문제가 코딩 테스트에 나올까 싶지만, 그래도 열심히 풀어보며 사고력을 꾸준히 높이는 것은 중요하다고 생각한다.