[Baekjoon] 32930/슈팅 연습/Python/파이썬/그리디 알고리즘

井·2025년 3월 6일

문제풀이

목록 보기

42/56

💡문제

FPS 게임 실력을 향상시키고 싶은 정우는 과녁 맞추기 훈련을 진행 중이다. 이 훈련에서 컴퓨터 화면을 2차원 좌표 평면으로 정의하여 과녁의 위치를 죄표로 나타낼 수 있다. 화면에서 오른쪽 방향으로 이동할수록 x 값이 증가하고 위쪽으로 이동할수록 y 값이 증가한다.

초기 상태에서 마우스 커서는 항상 (0, 0)에 위치하며, 컴퓨터 화면 위에는 N개의 과녁이 있다. 마우스 커서를 특정 과녁으로 이동하여 클릭하면 해당 과녁이 사라지고 점수를 얻게 된다. 이때 얻는 점수는 이동하기 전 마우스 커서의 위치에서 특정 과녁의 위치까지의 거리를 제곱한 값이다. 여기서 거리는 유클리드 거리로, 두 점 사이의 직선 거리를 의미한다.

과녁을 하나 없애면 새로운 과녁이 화면에 나타난다. 정우는 각 이동에서 현재 마우스 커서에서 가장 멀리 떨어진 과녁을 맞추는 전략을 사용한다. 이 과정을 M번 반복할 때, 정우가 얻는 총 점수를 구하자.

동일한 위치에 과녁이 나타나는 경우는 없으며, 각 이동 전에 마우스 커서에서 가장 먼 과녁은 항상 유일함이 보장된다.

입력

첫 번째 줄에 N과 M이 공백으로 구분되어 주어진다.(1 <= N, M <= 100)

두 번째 줄부터 N개의 줄에 걸쳐 현재 화면에 나타나 있는 과녁의 좌표를 나타내는 두 정수 x_i, y_i가 공백으로 구분되어 주어진다. (-100 <= x_i, y_i <= 100)
다음 M개의 줄에 걸쳐 다음에 나타날 과녁의 좌표를 나타내는 두 정수 x_j, y_j가 차례대로 주어진다. (-100 <= x_j, y_j <= 100)

출력

정우가 얻는 총 점수를 출력한다.

예제입력

예제출력

📖내가 작성한 Code

import sys

def distance_sq(i,j,x,y):
    return (i - x)**2 + (j - y)**2

def find_max_score(m, targets, new_targets):
    score = 0
    i = j = 0
    for cnt in range(m):
        targets.sort(key=lambda point: distance_sq(i,j,point[0],point[1]))
        x,y = targets.pop()
        score += distance_sq(i,j,x,y)
        i,j = x,y
        targets.append(new_targets[cnt])
    return score

def main():
    inputs = map(int, sys.stdin.read().split())
    n, m = next(inputs), next(inputs)
    targets = [(next(inputs), next(inputs)) for _ in range(n)]
    new_targets = [(next(inputs), next(inputs)) for _ in range(m)]
    sys.stdout.write(str(find_max_score(m, targets, new_targets)))

if __name__ == "__main__":
    main()

✍️풀이과정

처음에는 전체 탐색을 했었다. 그런데 구현하고 보니 시간 초과 날 듯해서 반신반의하면서 그냥 최대로 최대로 구현하니까 성공함.

여기에 대하여 문제에 브루트포스 알고리즘으로 분류해놨지만, 거리가 제곱만큼 더하기 때문에 기하급수적으로 올라가 선택할 때 항상 최대로 선택하면 되는 듯.

솔직히 잘 모르겠다. 그냥 마음가는데로 풀었음.
여기에 대하여 ai 한테 물어봄.

문제 분석 및 시간 복잡도 평가
브루트포스 접근법이 현실적인지 판단. 예를 들어 입력크기가 100인 경우 O(n^2)알고리즘은 10000번이면 충분하지만, O(2^n) 알고리즘은 O(N!)번의 연산이 필요하여 현실적으로 불가능.

따라서, 그리디나 DP와 분할 정복등을 생각할 수 있다. 그런데 DP는 경로가 계속 달라지는 이 문제에는 사용할 수 없음. 분할 정복으로는 이 문제가 상호 의존성이 높아서 분할 힘듬

그래서 그리디 알고리즘을 적용해라고 한다. 너무 어렵다. 열심히 해야겠다.

시간은 최대한 줄여서 순위권 등극

🧠 코드 리뷰

현재 코드는 매번 리스트를 정렬하여 가장 먼 과녁을 선택하는 방식을 사용하고 있습니다. 이는 시간 복잡도 측면에서 비효율적일 수 있으므로, 힙 자료구조를 활용하여 성능을 개선할 수 있습니다.
또한, pop() 사용 시 가장 먼 과녁을 정확히 선택하도록 인덱스를 명시하는 것이 좋습니다.

🛠️AI 개선 코드

import sys
import heapq

def distance_sq(i, j, x, y):
    return (i - x)**2 + (j - y)**2

def find_max_score(m, targets, new_targets):
    score = 0
    i = j = 0
    # 최대 힙을 사용하기 위해 음수로 저장
    max_heap = [(-distance_sq(i, j, x, y), x, y) for x, y in targets]
    heapq.heapify(max_heap)
    for cnt in range(m):
        # 가장 먼 과녁 선택
        dist, x, y = heapq.heappop(max_heap)
        dist = -dist  # 원래 거리로 복원
        score += dist
        i, j = x, y
        # 새로운 과녁 추가
        heapq.heappush(max_heap, (-distance_sq(i, j, new_targets[cnt][0], new_targets[cnt][1]), new_targets[cnt][0], new_targets[cnt][1]))
    return score

def main():
    inputs = map(int, sys.stdin.read().split())
    n, m = next(inputs), next(inputs)
    targets = [(next(inputs), next(inputs)) for _ in range(n)]
    new_targets = [(next(inputs), next(inputs)) for _ in range(m)]
    sys.stdout.write(str(find_max_score(m, targets, new_targets)))

if __name__ == "__main__":
    main()