선밥의 공부하는 블로그

당구 연습

문제 링크

당구 연습

분석

m은 당구대의 가로 길이, n은 세로 길이입니다.
startX, startY는 시작점으로 쳐야하는 공의 위치입니다.
balls는 매 회마다 쳐야하는 공의 위치입니다.

공은 직선으로만 이동하고, 입사각과 반사각이 같습니다.

공은 최소 한 번 벽에 부딪힌 후 목표 공에 도달해야합니다.

4개의 벽면을 맞추는 경우를 모두 탐색하고, 최소 거리를 구해볼 수 있습니다.

공이 벽에 부딪혀 반사되는 경로는, 목표 공을 해당 벽에 대해서 대칭시키고, 시작점에서 대칭점까지 직선으로 이동하는 것과 같습니다.
즉, 벽면을 기준으로 목표 공을 대칭이동 시키고, 시작점과의 거리를 계산하면 거리를 구할 수 있습니다.

벽면으로 가는 경로에 목표공이 존재하는 경우를 제외해주어야 합니다.

풀이

#include <vector>
#include <cmath>
#include <climits>

using namespace std;

// 시작점에서 목표점까지의 유클리드 거리의 제곱을 반환하는 함수
int getDistance(int startX, int startY, int x, int y)
{
    int dx = startX - x;
    int dy = startY - y;
    
    // 실제 거리는 sqrt(dx*dx + dy*dy)이다.
    return dx * dx + dy * dy;
}

vector<int> solution(int m, int n, int startX, int startY, vector<vector<int>> balls) {
    // 각 회마다 머쓱이가 친 공이 굴러간 거리의 최솟값의 제곱을 저장한다.
    vector<int> answer;
    
    // 맞춰야하는 공들의 위치를 순회
    for (const auto& ball : balls)
    {
        int targetX = ball[0];
        int targetY = ball[1];
        int minDist = INT_MAX;
        
        // 상단 벽에 부딪혀 목표 공에 도달할 경우
        // 시작점이 target보다 아래에 있는 경우 제외
        if (!(startX == targetX && startY < targetY))
        {
            minDist = min(minDist, getDistance(startX, startY, targetX, n + n - targetY));
        }
        
        // 하단 벽에 부딪혀 목표 공에 도달할 경우
        // 시작점이 target보다 위에 있는 경우 제외
        if (!(startX == targetX && startY > targetY))
        {
            minDist = min(minDist, getDistance(startX, startY, targetX, -targetY));
        }
        
        // 좌측 벽에 부딪혀 목표 공에 도달할 경우
        // 시작점이 target보다 오른쪽에 있는 경우 제외
        if (!(startY == targetY && startX > targetX))
        {
            minDist = min(minDist, getDistance(startX, startY, -targetX, targetY));
        }
        
        // 우측 벽에 부딪혀 목표 공에 도달할 경우
        // 시작점이 target보다 왼쪽에 있는 경우 제외
        if (!(startY == targetY && startX < targetX))
        {
            minDist = min(minDist, getDistance(startX, startY, m + m - targetX, targetY));
        }
        
        answer.push_back(minDist);
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(b)$입니다.

  • 맞춰야하는 공들의 위치를 순회하는 반복문 $O(b)$
    • b는 balls의 크기
  • 각 공마다 최대 4번의 거리 계산 $O(4)$
  • $O(b \times 4)$

공간 복잡도는 $O(b)$입니다.

  • 각 회마다 머쓱이가 친 공이 굴러간 거리의 최솟값의 제곱을 저장한 배열 answer $O(b)$
테스트 성능

테스트 1 〉 통과 (0.21ms, 4.21MB)
테스트 2 〉 통과 (0.23ms, 4.14MB)
테스트 3 〉 통과 (0.04ms, 4.01MB)
테스트 4 〉 통과 (0.12ms, 3.8MB)
테스트 5 〉 통과 (0.04ms, 4.19MB)
테스트 6 〉 통과 (0.18ms, 4.2MB)
테스트 7 〉 통과 (0.20ms, 4.21MB)
테스트 8 〉 통과 (0.05ms, 4.14MB)
테스트 9 〉 통과 (0.07ms, 4.15MB)
테스트 10 〉 통과 (0.33ms, 3.89MB)
테스트 11 〉 통과 (0.22ms, 3.68MB)
테스트 12 〉 통과 (0.21ms, 4.21MB)
테스트 13 〉 통과 (0.23ms, 3.96MB)
테스트 14 〉 통과 (0.05ms, 4.21MB)
테스트 15 〉 통과 (0.13ms, 3.77MB)
테스트 16 〉 통과 (0.11ms, 4.15MB)
테스트 17 〉 통과 (0.08ms, 3.77MB)
테스트 18 〉 통과 (0.11ms, 4.22MB)
테스트 19 〉 통과 (0.15ms, 4.21MB)
테스트 20 〉 통과 (0.17ms, 4.14MB)
테스트 21 〉 통과 (0.18ms, 4.29MB)
테스트 22 〉 통과 (0.22ms, 3.73MB)
테스트 23 〉 통과 (0.07ms, 4.2MB)
테스트 24 〉 통과 (0.16ms, 4.16MB)
테스트 25 〉 통과 (0.17ms, 4.15MB)
테스트 26 〉 통과 (0.13ms, 4.19MB)
테스트 27 〉 통과 (0.04ms, 4.21MB)
테스트 28 〉 통과 (0.20ms, 4.14MB)
테스트 29 〉 통과 (0.01ms, 4.16MB)
테스트 30 〉 통과 (0.01ms, 4.05MB)
테스트 31 〉 통과 (0.21ms, 4.21MB)
테스트 32 〉 통과 (0.42ms, 3.91MB)
테스트 33 〉 통과 (0.04ms, 4.14MB)
테스트 34 〉 통과 (0.12ms, 4.24MB)
테스트 35 〉 통과 (0.04ms, 4.13MB)
테스트 36 〉 통과 (0.21ms, 3.91MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

최근 글