나만의 작은 도서관

문제 140107. 점 찍기 본문

프로그래머스 문제풀이/코드카타

문제 140107. 점 찍기

pledge24 2024. 8. 8. 10:08

문제 링크

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

난이도 : Lv.2

 

문제 요약 설명

좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있습니다. 진수는 두 양의 정수 k, d가 주어질 때 다음과 같이 점을 찍으려 합니다.

  • 원점(0, 0)으로부터 x축 방향으로 a*k(a = 0, 1, 2, 3 ...), y축 방향으로 b*k(b = 0, 1, 2, 3 ...)만큼 떨어진 위치에 점을 찍습니다.
  • 원점과 거리가 d를 넘는 위치에는 점을 찍지 않습니다.

예를 들어, k가 2, d가 4인 경우에는 (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (4, 0) 위치에 점을 찍어 총 6개의 점을 찍습니다.

정수 k와 원점과의 거리를 나타내는 정수 d가 주어졌을 때, 점이 총 몇 개 찍히는지 return 하는 solution 함수를 완성하세요.

입력

  • 정수 k
  • 원점과의 거리를 나타내는 정수 d

입력 제한

  • 1 ≤ k ≤ 1,000,000
  • 1 ≤ d ≤ 1,000,000

입력 예제

// input
2 4               // k d

// ans
6

 

풀이 방식

이 문제는 수학적인 접근이 필요한 문제이다. 최적화를 요구하는 부분도 없지 않아 있지만, 의도만 정확히 파악한다면 최적화를 위한 추가적인 고민을 하지 않아도 된다. 

우선, 이 문제에서 우리가 구해야 할 것은 원점으로부터 거리가 d이하인 영역에서 (w*k, h*k)좌표 (k=0,1,2,3...)에 점을 찍고 찍을 수 있는 점들의 개수를 구하는 것이다. 따라서, 피타고라스의 정리(w^2 + h^2 = d^2)를 활용하여 높이 h를 구하고, h이하에서 찍을 수 있는 점들을 0~w범위에서 구해주면 된다. 당연히 w좌표는 k*0, k*1, k*2....처럼 k배수에 있는 좌표만 구한다.

위 과정을 반복할 때마다 구한 점들의 개수를 더해주며 문제에서 요구하는 찍을 수 있는 모든 점들의 개수를 구하면 정답이 된다.

 

정답 코드 

더보기
#include <string>
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

double getHeight(long long distance, long long w){
    if(w == distance) return 0;
    
    return sqrt(distance*distance - w*w);
}

long long solution(int k, int d) {
    long long answer = 0;
    
    for(int w = 0; w <= d; w+=k){
        long long height = floor(getHeight(d, w));
        answer += height / k + 1;
    }
    return answer;
}