[프로그래머스/C++] 당구 연습

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 당구의 원쿠션 규칙에 따라 공을 맞췄을 때, 공의 이동거리를 구하는 문제다.

 

여기서 시작하는 X좌표나 Y좌표가 같은 경우만 주의하면 쉽게 풀 수 있는 문제다.

 

아래 그림을 보며 기본적인 문제 풀이 방법을 생각해보자

 

벽에 부딪혀 반사된 공의 이동거리는 위 그림의 d와 같다.

 

즉, 맞추려는 공을 종이접기 하듯이 펼친 후 직선거리를 구하면 그 값이 공의 이동거리가 된다.

 

위 그림의 경우 위쪽 벽에 맞고 공을 맞출 때 이동거리를 구하면 아래와 같다.

$$ (distance)^2 = (x_i-x_s)^2 + (n-y_s+n-y_i)^2 $$

 

이렇게 4방향의 벽에 튀었을 때, 이동거리의 최소 값을 구하면 된다.

 

+ 만약 startX와 목표하는 공의 x좌표가 같다면, 두 공의 x좌표의 크기를 비교한 뒤 왼쪽으로만 쿠션을 할 수 있는지 오른쪽으로만 쿠션을 할 수 있는지 판단하면 된다. (Y좌표가 같은 경우도 마찬가지)

 

 

​

[아이디어 정리]

1. 입사각 반사각의 원리에 의해 공의 이동거리는 쿠션을 하려는 벽을 기준으로 종이접기 하듯이 펼친 후 두 공을 이은 직선거리와 같다.
2. 좌표가 같은 경우는 크기를 비교해 공을 튀길 수 있는 방향의 벽만 고려하도록 코드를 구현한다.

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <cmath>
#include <iostream>

using namespace std;

vector<int> solution(int m, int n, int startX, int startY, vector<vector<int>> balls) {
    vector<int> answer;
    int distX,distY,temp,minAns;
    for (int i=0; i<balls.size(); i++)
    {
        vector<int> nb=balls[i];
        minAns=10000000, distX=pow(startX-nb[0],2), distY=pow(startY-nb[1],2);
        if (startX!=nb[0])
        {
            temp=distX+pow(startY+nb[1],2), minAns=min(minAns,temp); // 아래 튀기기
            temp=distX+pow(n-startY+n-nb[1],2), minAns=min(minAns,temp); // 위 튀기기
        }
        else
        {
            if (startY<nb[1]) //아래쪽 튀기기만 가능
                temp=distX+pow(startY+nb[1],2), minAns=min(minAns,temp); // 아래 튀기기
            else
                temp=distX+pow(n-startY+n-nb[1],2), minAns=min(minAns,temp); // 위 튀기기
        }
        if (startY!=nb[1])
        {
            temp=distY+pow(startX+nb[0],2), minAns=min(minAns,temp); // 왼쪽 튀기기
            temp=distY+pow(m-startX+m-nb[0],2), minAns=min(minAns,temp);
        }
        else
        {
            if (startX<nb[0]) //왼쪽 튀기기만 가능
                temp=distY+pow(startX+nb[0],2), minAns=min(minAns,temp); // 왼쪽 튀기기
            else
                temp=distY+pow(m-startX+m-nb[0],2), minAns=min(minAns,temp);
        }
        answer.push_back(minAns);
    }
    return answer;
}

 

---

그림을 그려서 잘 생각하면 쉽게 풀 수 있는 문제였다.

 

프로그래머스