나만의 작은 도서관
문제 140107. 점 찍기 본문
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/140107
난이도 : 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;
}
'프로그래머스 문제풀이 > 코드카타' 카테고리의 다른 글
문제 81302. 거리두기 확인하기 (0) | 2024.08.10 |
---|---|
문제 148653. 마법의 엘리베이터 (0) | 2024.08.09 |
문제 155651. 호텔 대실 (0) | 2024.08.07 |
문제 12978. 배달 (2) | 2024.08.06 |
문제 86971. 전력망을 둘로 나누기 (0) | 2024.08.05 |