점 찍기(30분)

1번. 점 찍기
https://school.programmers.co.kr/learn/courses/30/lessons/140107

30분 동안 문제 하나 풀고 하나 공부하니 긴 집중력이 필요한 코딩테스트에서 역량이 부족한 듯하여 혼자 하는 코딩테스트이다.

2시간 동안 3문제를 풀었다.

첫 번째 문제는 점 찍기 문제. 25점을 맞았다... 형변환과 시간 초과가 문제였다. 형변환은 고쳤지만 시간 초과로 결국 81.3점인 풀이다.
구현 아이디어 7분 구현 23분

풀이(시간 초과)

가능한 경우를 완전 탐색하니 시간 초과는 당연한 일이다. 7분 동안 다른 방법을 찾으려고 노렸했지만 7분에 마음이 급해져 일단 완전 탐색을 했다.

• 1 <= k <= 1,000,000 1 <= d <= 1,000,000이기 때문에 길이를 구하는 부분에서 int형은 불가능하다. long 타입 형변환이 필요하다.

#include <string>
#include <vector>

using namespace std;

long long solution(int k, int d) {
    long long answer = 0;
    
    for(long i = 0; i <= d; i += k)
    {
        for(long j = 0; j <= d; j += k)
        {
            long len = i * i + j * j;
            if((long)d*d >= len) ++answer;
        }
    }
    
    return answer;
}

---

풀이

1. x 좌표의 값을 vector에 담는다.
2. 하나씩 돌며 해당 x 좌표에 가능한 y 좌표의 최대값을 구한다.
3. 최대 y에서 k를 나눈 몫이 규칙에 따라(k씩 더해가는 규칙) 가능한 최대 y값.
4. y 좌표의 0은 들어가지 않기 때문에 answer에 더할 때 +1 한다.

#include <string>
#include <vector>
#include <math.h>

using namespace std;

long long solution(int k, int d) {
    long long answer = 0;
    
    vector<int> vecX;
    int tmp = 0;
    while(tmp <= d)
    {
        vecX.push_back(tmp);
        tmp += k;
    }
    
    for(int i = 0; i < vecX.size(); ++i)
    {
        // x 좌표.
        int x = vecX[i];
        
        // 가능한 최대 y 좌표.
        // y*y = d*d - x*x;
        int maxY = sqrt((long)d*d - (long)x*x);
        answer += maxY / k + 1;
    }
    
    return answer;
}