백준 - 2891 카약과 강풍

[Silver V] 카약과 강풍 - 2891

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

그리디 알고리즘, 구현

제출 일자

2024년 4월 2일 18:25:55

문제 설명

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

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

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

입력

첫째 줄에 팀의 수 N, 카약이 손상된 팀의 수 S, 카약을 하나 더 가져온 팀의 수 R이 주어진다. (2 ≤ N ≤ 10, 1 ≤ S, R ≤ N)

둘째 줄에는 카약이 손상된 팀의 번호가 주어진다. 팀 번호는 중복되지 않는다.

셋째 줄에는 카약을 하나 더 가져온 팀의 번호가 주어진다. 팀 번호는 중복되지 않는다.

출력

첫째 줄에 출발을 할 수 없는 팀의 최솟값을 출력한다.

풀이과정

그리디 문제로 로직 자체는 쉽지만 어딘가 꼬이는 부분이 있으면 계속 맞왜틀을 하게 되는 문제이다. 처음에 ans = R로 하고 카약을 빌릴 수 있으면 ans를 감소시켜줬었는데 이 부분에서 꼬였었다. i번째 팀의 카약이 손상되고, i번째 팀에게 여분 카약이 있는 경우에도 ans를 감소시켜줘야 했는데 그 부분을 고려하지 않았었다. 그래서 그냥 마지막에 반복문을 돌려서 ans를 세는 것으로 고쳐서 맞았다.

프로그래머스의 체육복 문제와 유사하다.

카약의 갯수 증감

먼저 a라는 배열을 선언해주었다.

1. a[i] = 0 : 카약을 정상적으로 탈 수 있는 팀
2. a[i] < 0 : 카약을 빌려야하는 팀
3. a[i] > 0 : 카약을 빌려줄 수 있는 팀

카약이 손상된 S개의 팀에 대한 입력을 받고, 여분 카약이 있는 R개 팀을 입력받는다. 이 때 입력받는 팀의 a[i]의 값을 조정해준다.

카약 빌려주기

1번부터 N번까지 팀을 조회하며, a[i] < 0인 팀은 인접한 팀으로부터 카약을 빌린다. 이때 i-1번 팀의 카약을 빌리는 것이 우선시 되며, 그렇지 못하면 i+1번 팀의 카약을 빌릴 수 있는지 확인한다.
카약을 빌릴 수 있다면 a배열 값을 조정한다.

정답 구하기

1번부터 N번까지 팀을 조회하며 카약 빌리기가 끝나고도 a[i] < 0인 팀을 센다.

코드

#include <iostream>
using namespace std;
int N, S, R, x, ans;
int a[15];
int main(void) {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> S >> R;
    while (S--) {
        cin >> x;
        a[x]--;
    }
    while (R--) {
        cin >> x;
        a[x]++;
    }
    for (int i = 1; i <= N; i++) {
        if (a[i] < 0) {
            if (i > 1 && a[i - 1] > 0) {
                a[i]++;
                a[i - 1]--;        
            }
            else if (i < N && a[i + 1] > 0) {
                a[i]++;
                a[i + 1]--;
            }
        }
    }
    for (int i = 1; i <= N; i++)if (a[i] < 0) ans++;
    cout << ans;
}