프로그래머스 - 점 찍기

lv. 2 단계의 코딩 테스트 연습 문제 중 '점 찍기'에 대한 풀이를 설명하고 있습니다.

 

프로그래머스 - 점 찍기

 

코딩 테스트 연습 문제 풀이

 

1. 원리

2. 코드

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 원리는 아주 간단하다.
• 다 풀고 나서 질문하기를 봤는데, 굉장히 수학적으로 푸신 분들이 있는데 그런 풀이를 보면서 주눅들 필요가 없다고 얘기하고 싶다.
• 우리는 피타고라스 정리를 알고 있으므로 쉽게 풀 수 있다.
• (0, 0)을 기준으로 거리가 d보다 작은 곳에 점들을 찍어야 하므로 임의의 좌표를 (x, y)라고 했을 때 다음의 식을 만족해야 한다.
  • x^2 + y^2 = d^2 
• 아, 애초에 모든 조합을 해보는 것은 k가 1일 때, 1,000,000 의 숫자가 나올 수 있기 때문에 고려하면 안된다.
• x 또는 y가 0이 될 때, x나 y 자리에 올 수 있는 숫자들을 먼저 구한다.
  • x^2 = d^2 이거나
  • y^2 = d^2 이 성립해야 한다.
  • 그러므로, x 나 y 자리에 대입될 수 있는 숫자들은 동일한 집합이라고 생각할 수 있다.
  • 정확하게 범위로 나타내면 x나 y의 범위는 다음과 같다.
  • 0 <= x, y <= d
  • 문제처럼 k가 2이고, d가 4이면, 0 <= x, y <= 4 를 만족해야 한다
    • x나 y 자리에 올 수 있는 숫자는 {0, 2, 4} 이렇게 세 가지이다.
• 우리는 이제 x에 0을 선택했을 때, y에 어떤 수가 올 수 있는지 선택해야한다.
• 하지만 아까 얘기한 바와 같이 일일히 대입하기에는 시간 복잡도를 초과할 수 있다.
• 떠올릴 수 있는 아이디어는 x에 어떤 값을 선택했을 때, y에 올 수 있는 수들의 개수를 바로 알 수 있으면 된다!!
• 예를 들어, 위의 예제에서 x가 0이라면 피타고라스 정리에 의해서 y에 올 수 있는 최대 숫자는 4이다.
• 따라서 0~4라는 범위에 a x k 로 만들어지는 숫자가 몇 개가 있는지만 알면 된다.
• 나는 누적합 배열을 만들어서 풀이했다.
  • 아까 예제처럼 0, 2, 4의 숫자를 만들 수 있다면 누적합 배열은 아래와 같다.

	0	1	2	3	4
누적합	1	1	2	2	3

• 0이라는 숫자는 항상 만들어질 수 있으므로 1개이다.
• 1까지의 범위 내에서는 1이 만들어질 수 없으므로, 그대로 1개이다.
• 2까지의 범위 내에서는 0, 2가 만들어질 수 있으므로 2개이다.
• 3까지의 범위 내에서는 0, 2가 만들어질 수 있으므로 2개이다.
• 4까지의 범위 내에서는 0, 2, 4가 만들어질 수 있으므로 4개이다.
• 자 그럼 이제 예제를 풀어보자
  • x에 0을 선택한 경우
    • y에 올 수 있는 최댓값은 4이므로, 4까지의 범위 내에서 만들어진 숫자는 {0, 2, 4} 이다.
    • 즉, 3개이다.
  • x에 2를 선택한 경우
    • y에 올 수 있는 최댓값은 2이므로, 2까지의 범위 내에서 만들어진 숫자는 {0, 2} 이다.
    • 즉, 2개이다.
  • x에 4를 선택한 경우
    • y에 올 수 있는 최댓값은 0이므로, 0까지의 범위 내에서 만들어진 숫자는 {0} 이다.
    • 즉, 1개이다.
• 이렇게 구한 수를 다 더하면 k가 2이고 d가 4일 때, 찍을 수 있는 좌표의 수는 6개임을 알 수 있다.

코드

import math
def solution(k, d):
    answer = 0
    count = [0 for _ in range(1000001)]
    count[0] = 1

    limitation = d**2
    a = 1

    make = []
    make.append(0)
    for i in range(1, d+1):
        if (a*k)**2 > limitation:
            count[i] = count[i-1]
        if i == a*k:
            make.append(a*k)
            count[i] = count[i-1] + 1
            a += 1
        else:
            count[i] = count[i-1]
    for number in make:
        result = limitation - number**2
        result = int(math.sqrt(result))
        answer += count[result]
    return answer

 

너무 어렵게 생각하지 않아도 충분히 풀 수 있는 문제였다.