점 찍기
문제설명
좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있습니다. 진수는 두 양의 정수 k, d가 주어질 때 다음과 같이 점을 찍으려 합니다.
- 원점(0, 0)으로부터 x축 방향으로 ak(a = 0, 1, 2, 3 ...), y축 방향으로 bk(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 함수를 완성하세요.
제한사항
- 1 ≤ k ≤ 1,000,000
- 1 ≤ d ≤ 1,000,000
입출력 예1
Input : 2, 4
Output : 6입출력 예2
Input : 1, 5
Output : 26문제풀이1 (시간초과)
해당 문제에 대해서 BFS 탐색으로 접근을 하였다. (0, 0)좌표부터 시작해서 방문한 이력이 있는지 체크하고, 4방향으로 이동하면서 거리가 d보다 작은지 체크를 했다. 문제는 풀 수 있었지만, 제한사항을 보면 k와 d가 1,000,000까지이다. 즉, 시간 초과가 나타날 수 밖에 없었다. 그래서 더 간소화하게 풀어야함을 느꼈다.
코드1 (시간초과)
import math
from collections import deque
# 경계선 체크
def checkBorder(x, y, max):
if x < 0 or x > max or y < 0 or y > max:
return False
return True
# 거리 구하는 함수
def getDistance(x, y):
return math.sqrt((x - 0) ** 2 + (y - 0) ** 2)
# bfs 탐색
def bfs(x, y, visited, k, d):
dx = [-1, 1, 0, 0] # x방면 이동
dy = [0, 0, -1, 1] # y방면 이동
queue = deque() # 큐 생성
queue.append((x, y)) # 큐 삽입
visited[x][y] = 1 # 방문 기록
result = 1 # 정답 1로 초기화
while queue:
a, b = queue.popleft()
for i in range(4):
na = a + (dx[i] * k) # k만큼 이동
nb = b + (dy[i] * k) # k만큼 이동
if checkBorder(na, nb, d):
if visited[na][nb] == 0 and getDistance(na, nb) <= d: # 방문한 적 없고, 거리가 d미만인 경우
queue.append((na, nb)) # 큐삽입
visited[na][nb] = 1 # 방문 기록
result += 1 # 정답 추가
return result
# 한개빼고 시간 초과
def solution1(k, d):
answer = 0
visited = [[0] * (d + 1) for _ in range(d + 1)]
answer = bfs(0, 0, visited, k, d)
return answer
print(solution1(2, 4))
print(solution1(1, 5))문제풀이2 (시간초과)
제한사항을 보고 BFS탐색을 쓰면 안되겠다 생각을 해서 x좌표에 대해서 먼저 생각하기로 했다. 두 좌표 (x1, y1), (x2, y2)사이의 거리는 아래와 같다.
d^2 = (x2 - x1)^2 + (y2 - y1)^2위 식을 이용해서 x값을 이용해서 나올 수 있는 최대 y값을 이용해 for문으로 탐색하며 해결하고자 했다. 코드는 아래와 같다.
코드2 (시간초과)
import math
# 4개빼고 시간 초과
def solution2(k, d):
answer = 0
for x in range(0, d + 1, k): # k step만큼 비교
maxY = math.floor(int(math.sqrt(d ** 2 - x ** 2))) # 최대 max y값은 d(거리)^2 - x의 좌표^2의 루트하고 내림한 값
for y in range(0, maxY + 1, k): # k step만큼 허용 y값 추가
answer += 1
return answer
print(solution2(2, 4))
print(solution2(1, 5))문제풀이3 (정답)
생각해보니 굳이 for문을 쓸 필요가 없었다. 최대 y값이 나온다면 그 값을 k로 나눠서 몫 + 1을 하면 됐다. 1을 더하는 이유는 x좌표 0을 위해서이다. 코드는 아래와 같다.
코드3 (정답)
import math
# 성공
def solution3(k, d):
answer = 0
for x in range(0, d + 1, k):
maxY = math.floor(int(math.sqrt(d ** 2 - x ** 2))) # 최대 max y값은 d(거리)^2 - x의 좌표^2의 루트하고 내림한 값
answer += (maxY // k) + 1 # k 스템만큼 나누고 난 뒤 더하기 1(y좌표가 0인 경우 추가)
return answer
print(solution3(2, 4))
print(solution3(1, 5))