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

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

 

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

프로그래머스

---

 

해결 전략

 

수학

 

#include <iostream>
using namespace std;

long long solution(int k, int d) {
    long long answer = 0;

	for(int a = 0; a * k <= d; a++)
	{
		for(int b = 0; b * k <= d; b++)
		{
			long long dist = pow(a * k, 2) + pow(b * k, 2);
			
            if (dist <= d * d)
				answer++;	
		}
	}

	return answer;
}

 

먼저 (a * k)^2 + (b * k)^2 <= d * d  공식을 떠올림

문제에서 1 ≤ d ≤ 1,000,000 이라고 주어졌기 때문에 이중 for문을 사용하면 시간초과가 나옴을 인지.

 

for문 하나를 없애기 위해

(b * k) <= sqrt( d * d -  (a * k)^2 ) 임을 사용하고 b * k를 사용하지 않는 방법을 떠올림.

---

 

정답 코드

 

#include <iostream>
#include <cmath> // sqrt, pow 사용을 위한 헤더
using namespace std;

long long solution(int k, int d) {
    long long answer = 0; 

	for(int a = 0; a * k <= d; a++)
	{
		// yy = x좌표가 a * k일 때 범위 내에 가질 수 있는 y좌표의 최대값
		// 이는 원의 방정식을 이용하여 유도된 것으로, 원의 중심에서 x축까지의 거리가 a*k일 때, 원 위의 점의 y좌표 값을 구하는 것이다.
		long long yy = sqrt((long long)d * d - pow(a * k, 2));

		// 해당 x 좌표에서 가능한 y 좌표의 개수를 answer에 더한다.
		// 이 때, y 좌표의 개수는 해당 높이를 k로 나눈 몫에 1을 더한 값이다(y=0인 경우 더하기). 
		answer += (yy / k + 1);
	}

	return answer; // 결과값 반환
}

 

 

 

※ 주의할 점

long long yy = sqrt((long long)d * d - pow(a * k, 2));

 

d가 100만 이하의 수이기 때문에 d * d 연산 시 int overflow가 날 수 있다.

(long long) d * d로 명시적 캐스팅으로 overflow를 방지해야 한다.

 

---