백준 15752번 Hoofball

문제 링크입니다: https://www.acmicpc.net/problem/15752

같은 학교 학우들이신 Green55님과 degurii님은 DFS를 이용하여 푼 문제였지만 저는 다음 소를 지정하는 함수만을 이용하여 풀었던 문제였습니다.

알고리즘은 아래와 같습니다.

1. 소들의 좌표를 오름차순으로 정렬합니다.

2. 모든 소들을 선택하여 다음 소에게 공을 전달하도록 하고 공을 전달 받은 소들을 표시합니다.

3. 다시 모든 소들을 순회하는데 한번도 공을 전달 받지 않은 소들은 꼭 공을 사람으로부터 받아야합니다.

-> 또한 서로에게만 공을 주는 소들에 대한 쌍들 또한 공을 사람으로부터 받아야합니다.

4. 3번에서 계산한 공들의 합을 출력해줍니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 100 + 1;

const int INF = 987654321;

 

int N;

int arr[MAX];

int passed[MAX];

 

//다음 공을 전달해줄 소

int nextCow(int idx)

{

        if (idx == 0)

                 return idx + 1;

        else if (idx == N - 1)

                 return idx - 1;

        else

        {

                 int leftDistance = arr[idx] - arr[idx - 1];

                 int rightDistance = arr[idx + 1] - arr[idx];

 

                 if (leftDistance <= rightDistance)

                         return idx - 1;

                 else

                         return idx + 1;

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> arr[i];

 

        sort(arr, arr + N);

 

        //한 번씩 패스를 시켜본다

        for (int i = 0; i < N; i++)

                 passed[nextCow(i)]++;

 

        int ball = 0;

        for (int i = 0; i < N; i++)

        {

                 //한번도 공을 받지 않은 소

                 if (!passed[i])

                         ball++;

                 //서로 주고 받는 소들

                 if (i < nextCow(i) && nextCow(nextCow(i)) == i && passed[i] == 1 && passed[nextCow(i)] == 1)

                         ball++;

        }

 

        cout << ball << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~