백준 2891번 [카약과 강풍](C++) -yes6686- 티스토리

백준 문제 풀이: 2891 [카약과 강풍]

---

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

문제 설명:

카약이 파손된 팀이 다른 팀의 여분 카약을 빌려 최종적으로 경기 참가가 불가능한 팀 수를 최소화하는 문제입니다. 총 \(n\)개의 팀 중 일부는 카약이 파손되었고(\(-1\)), 일부는 여분 카약을 가지고 있습니다(\(+1\)). 여분 카약은 인접한 팀에만 빌려줄 수 있습니다.

---

문제 해결 코드

// 카약과 강풍 문제 해결 코드
#include <iostream>
using namespace std;

int arr[11]; // 각 팀의 카약 상태 저장 배열 (-1: 파손, 0: 정상, 1: 여분)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);    

    int n, s, r;
    cin >> n >> s >> r;

    int x;
    // 파손된 팀 입력 처리
    for (int i = 0; i < s; i++) {
        cin >> x;
        arr[x] = -1;
    }

    // 여분 카약이 있는 팀 입력 처리
    for (int i = 0; i < r; i++) {
        cin >> x;
        arr[x]++;
    }

    // 여분 카약 빌려주기
    for (int i = 1; i <= n; i++) {
        if (arr[i] == 1) { // 여분이 있는 팀
            if (arr[i - 1] == -1) { // 이전 팀이 파손된 경우
                arr[i] = 0;
                arr[i - 1] = 0;
            } else if (arr[i + 1] == -1) { // 다음 팀이 파손된 경우
                arr[i] = 0;
                arr[i + 1] = 0;
            }
        }
    }

    // 최종적으로 경기 불참 팀 계산
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (arr[i] == -1) ans++;
    }

    cout << ans << '\n';
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘:
  • 여분의 카약을 가지고 있는 팀이 인접한 파손된 팀에 우선적으로 빌려줍니다.
  • 빌려준 뒤에는 해당 팀과 파손된 팀 모두 정상 상태로 변경합니다.
• 구현 세부사항:
  • arr: 각 팀의 카약 상태를 저장하는 배열로, 초기 상태는 0입니다. 파손된 팀은 -1, 여분 카약을 가진 팀은 +1로 설정합니다.
  • 여분 카약을 가진 팀(arr[i] == 1)이 인접한 파손된 팀(arr[i-1] == -1 또는 arr[i+1] == -1)에 빌려줍니다.
  • 경기 참가 불가능한 팀 수는 배열에서 -1의 개수를 세어 계산합니다.
• 시간 복잡도 분석:
  • 배열 초기화 및 입력 처리: \(O(n)\)
  • 여분 카약 처리: \(O(n)\)
  • 불참 팀 계산: \(O(n)\)
  • 전체 시간 복잡도: \(O(n)\)

---

결과

이 알고리즘은 최소한의 경기 불참 팀 수를 계산합니다. 예를 들어:

• 입력:

          5 2 2
          2 4
          1 3
          

• 출력: 0

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!