백준 2891 - 카약과 강풍

문제 설명

2890번을 보면 알겠지만, 상근이는 카약 대회를 개최했다. 그런데, 갑자기 엄청난 강풍이 경기장에 불었고, 일부 카약이 부서졌다. 경기는 5분 안에 시작해야 하는 상황이다.

다행히 일부 팀은 혹시 모를 사태에 대비해서 카약을 하나 더 경기장에 들고 왔다. 카약은 매우 무겁고 운반하기 어렵다. 따라서, 자신의 바로 다음이나 전에 경기하는 팀에게만 카약을 빌려주려고 한다. 즉, 팀 4는 여분의 카약을 3이나 5에게만 빌려줄 수 있다. 다른 팀에게서 받은 카약은 또 다른 팀에게 빌려줄 수 없다. 또, 카약을 하나 더 가져온 팀의 카약이 손상되었다면, 여분의 카약으로 경기에 출전하게되고, 이 카약은 다른 팀에게 빌려줄 수 없다.

카약이 부서진 팀과 하나 더 가져온 팀이 주어진다. 카약을 적절히 빌렸을 때 출발하지 못하는 팀의 최솟값은 몇 팀인지 구하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/2891

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 팀이 대회에 참여하였고 S개의 팀의 배가 부서졌으며 R개의 팀은 여분이 존재한다.

이때, 여분이 존재하는 팀이 인접해 있다면 배가 부서진 팀은 배를 빌려 대회에 참가할 수 있다.

참가하지 못하는 팀을 최소한으로 만들면 몇 팀인지 구해야 한다.

 

참가하지 못하는 팀을 최소로 만든다는 뜻은 최대한 많이 빌려야 한다는 뜻과 같다.

즉, 빌릴 수 있음에도 못 빌리는 일은 없어야 한다.

따라서, 한쪽으로 진행하며 진행하는 방향의 역순을 우선으로 배를 빌려주면 빠뜨리는 경우가 없을 것이다.

만약, 그렇지 않을 경우에는 반대쪽에 빌려줄 수 있는지 확인하며 진행하면 된다.

 

이를 구현하기 위해, 배를 소유하고 있는 개수를 전처리를 통해 미리 계산한다.

vector<int> teams(N + 1, 1);
for (int i = 0; i < S; i++)
{
    int s;
    cin >> s;
    teams[s]--;
}

for (int i = 0; i < R; i++)
{
    int r;
    cin >> r;
    teams[r]++;
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N, S, R;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(4);

    cin >> N >> S >> R;

    vector<int> teams(N + 1, 1);
    for (int i = 0; i < S; i++)
    {
        int s;
        cin >> s;
        teams[s]--;
    }

    for (int i = 0; i < R; i++)
    {
        int r;
        cin >> r;
        teams[r]++;
    }

    int ans = 0;
    for (int i = 1; i <= N; i++)
    {
        if (teams[i] > 1)
        {
            if (teams[i - 1] == 0)
            {
                teams[i]--;
                teams[i - 1]++;
            }
            else if(i < N && teams[i + 1] == 0)
            {
                teams[i]--;
                teams[i + 1]++;
            }
        }
    }

    for (int i = 1; i <= N; i++)
    {
        if (teams[i] == 0) ans++;
    }

    cout << ans;

    return 0;
}

---