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

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

2891번: 카약과 강풍

greedy 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

전체 팀 수 n, 카약이 부러진 팀 수 s, 여분 카약 가진 팀 수 r, 팀별 보유 현황 일차원 배열 kayak, 정답을 출력할 변수 ans를 선언 후 입력받습니다.* 카약의 여분이 있으나 부러질 수 있음을 고려해야 합니다. 따라서 처음 kayak을 1로 초기화 한 후 부러졌다면 1을, 여분이 있다면 1을 더해주는 방식으로 초기화 해줍니다.

📔 풀이과정

카약이 부러졌으나 여분이 있다면 고려해줄 필요가 없습니다. 카약을 빌려줄 수 없을 뿐더러 다른 팀에게 줄 필요가 없기 때문입니다.

왼쪽부터 오른쪽 팀 순으로 for loop를 수행하며 빌려 줄 수 있는 팀이라면 왼쪽과 오른쪽을 확인해 필요하다면 왼쪽팀부터 카약을 빌려줍니다. 

* 카약이 없는 팀만 확인해서 그 팀의 양 옆을 확인해 여분의 카약이 있는지 검사하는 로직은 틀리게 됩니다. 여분의 카약이 있는 팀이 어느쪽에 있는지 알 수 없기 때문에 어떤 서순으로 빌리는 것이 유리한지 알기 어렵습니다. 없는 팀의 왼쪽에 있거나 오른쪽에 있거나 양쪽 모두 가능하기 때문입니다. 

📔 정답출력

ans를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;

int n, s, r, kayak[12], ans;

int main(){
  cin >> n >> s >> r;

  for(int i = 1; i <= n; i++) {
    kayak[i] = 1;
  }

  for(int i = 0, teamNum; i < s; i++) {
    cin >> teamNum;
    kayak[teamNum]--;
  }

  for(int i = 0, teamNum; i < r; i++) {
    cin >> teamNum;
    kayak[teamNum]++;
  }

  for(int i = 1; i <= n; i++) {
    if(kayak[i] == 2){
      if(!kayak[i-1]) {
        kayak[i] = kayak[i-1] = 1;
        continue;
      }
    }
    if(kayak[i] == 2){
      if(!kayak[i+1]) {
        kayak[i] = kayak[i+1] = 1;
        continue;
      }
    }
  }

  for(int i = 1; i <= n; i++)
    if(!kayak[i])
      ans++;

  cout << ans;
}

---

📕 Test Case

몇 가지 반례입니다.

input
5 3 3
1 2 3
2 3 4
답 : 1

5 2 2
1 5
2 4
0