[백준][C++] 18221번 교수님 저는 취업할래요

교수님 저는 취업할래요

문제 링크

교수님 저는 취업할래요

분석

2차원 배열 $N \times N$에서 성규(2)와 교수님(5)의 위치를 찾은 뒤, 성규가 도망칠 수 있는 조건을 만족하는지 판단하는 문제입니다.

배열의 값 의미는 다음과 같습니다.

• 0: 빈값
• 1: 다른 학생
• 2: 성규
• 5: 교수님

도망칠 수 있으려면 다음 두 조건을 모두 만족해야합니다.

1. 성규와 교수님의 유클리드 거리가 5 이상일 경우
2. 성규와 교수님을 꼭짓점으로 하는 축에 평행한 직사각형 안에 다른 학생이 3명 이상 있을 경우
   • 성규와 교수님이 같은 행 또는 열에 있을 경우 직사각형 대신 두 점을 잇는 선분 위에 다른 학생이 3명 이상 있어야합니다.

필요한 값은 다음과 같습니다.

• 성규와 교수님의 위치
• 성규와 교수님의 거리
• 성규와 교수님 사이의 학생 수

위와 같은 값이 필요할 때 구현할 방법으로 다음과 같이 생각해 볼 수 있습니다.

1. 입력을 받으며 성규와 교수님의 위치를 저장한다.
2. 두 점 사이의 거리를 계산한다.
3. 거리가 5 미만일 경우 탈출하지 못하므로, 0을 출력한다.
4. 성규와 교수님 위치의 직사각형 크기에 학생 수를 센다.
5. 학생 수가 3명 이상이면 1, 아닐 경우 0을 출력한다.

풀이

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

using namespace std;

int main()
{
    int N;
    cin >> N;

    vector<vector<int>> TableArray(N, vector<int>(N, 0));
    pair<int, int> ProfessorIndex;
    pair<int, int> SungkyuIndex;

	// 입력을 받는 반복문
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> TableArray[i][j];

            // 교수님의 위치
            if (TableArray[i][j] == 5)
            {
                ProfessorIndex = { j, i };
            }
            // 성규의 위치
            else if (TableArray[i][j] == 2)
            {
                SungkyuIndex = { j, i };
            }
        }
    }

    // 거리 체크
    float DeltaX = SungkyuIndex.first - ProfessorIndex.first;
    float DeltaY = SungkyuIndex.second - ProfessorIndex.second;

    float SquaredDeltaX = pow(DeltaX, 2.0f);
    float SquaredDeltaY = pow(DeltaY, 2.0f);

    float Distance = sqrt(SquaredDeltaX + SquaredDeltaY);

    // 도망 갈 수 없는 거리일 경우
    if (Distance < 5)
    {
        cout << 0 << endl;

        return 0;
    }

    // 학생이 세 명 이상 있는지 체크
    int MinX = min(ProfessorIndex.first, SungkyuIndex.first);
    int MinY = min(ProfessorIndex.second, SungkyuIndex.second);

    int StudentCount = 0;
    for (int i = 0; i <= abs(DeltaY); ++i)
    {
        for (int j = 0; j <= abs(DeltaX); ++j)
        {
            if (TableArray[MinY + i][MinX + j] == 1)
            {
                ++StudentCount;
            }
        }
    }

    if (StudentCount < 3)
    {
        cout << 0 << endl;

        return 0;
    }

    cout << 1 << endl;

    return 0;
}

성능 요약

시간 복잡도는 $O(n^{2})$입니다.

• 교실에 대한 정보를 입력받는 반복문 $O(n^{2})$
• 두 점 사이의 학생 수를 세는 반복문 $O(n^{2})$
• $O(n^{2}) + O(n^{2})$

공간 복잡도는 $O(n^{2})$입니다.

• 교실 크기만큼의 배열 TableArray $O(n^{2})$

메모리: 5864 KB

시간: 184 ms