백준 2891번 - 카약과 강풍 (C++)

유형: 그리디

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

2891번: 카약과 강풍

 

풀이

문제 기준 인덱스 시작이 0인지 1인지 잘 봐야한다. 이 문제는 1부터 시작하기에 벡터에 넣을 때 1씩 빼주었다.

벡터는 N개의 원소의 값을 모두 1로 초기화하고, 없는 팀은 -1 연산, 여분 팀은 +1 연산을 한다.

그후 벡터의 원소를 하나씩 돌면서, 여분 팀을 기준으로 연산한다.

여분 팀의 앞팀이 없는 경우에는 앞팀을 먼저 빌려주고 끝난다.

여분 팀의 뒤팀만 없는 경우에만 뒤팀을 빌려주게 된다.

앞팀과 뒤팀을 찾을 때 인덱스가 벡터 범위를 벗어나는지 확인하는것도 잊지 말자.

#include "iostream"
#include "vector"

using namespace std;

int main(){
    ios::sync_with_stdio(0);

    int answer = 0;
    int n, s, r; cin >> n >> s >> r;

    vector<int> team(n, 1);

    while (s--){ // 없는 팀 갱신
        int temp; cin >> temp;
        team[temp-1]--;
    }

    while (r--){ // 여분 팀 갱신
        int temp; cin >> temp;
        team[temp-1]++;
    }

    // 빌려주기
    for(int i = 0; i < n; i++){
        if(team[i] > 1){ // 본인이 여분이 있을 때
            if(i-1 > -1 && team[i-1] < 1){
                // 앞쪽에 빌려주는 경우
                team[i-1]++;
                team[i]--;
            } else if(i+1 < n && team[i+1] < 1){
                // 뒤쪽에 빌려주는 경우
                team[i+1]++;
                team[i]--;
            }
        }
    }

    // 정답 카운트
    for(auto now: team){
        if(now == 0) answer++;
    }

    cout << answer << endl;

    return 0;
}