[C++ 풀이] 2810번. 컵홀더

 

문제 분석

좌석배치에 따라 컵홀더 개수가 달라지며, 컵홀더를 사용할 수 있는 사람 수를 구하는 문제이다.

S는 일반 좌석, L은 커플석이며 L은 항상 쌍으로 두 좌석이 붙어있다. 

양 끝좌석에는 컵홀더가 무조건 존재한다. 

이러한 특징에 따라 코드를 구성했다. 

 

알고리즘 설계

우선 string형으로 좌석을 입력받았다. 

그리고 for문으로 좌석중에 'S'가 있다면 일반좌석 수(cnts)를 카운팅, 아니라면 커플석이므로 커플석 수(cntl)를 카운팅했다. 

이때 커플석은 무조건 두 좌석이 붙어있으므로, 커플석좌석을 다 구한 뒤에는 2로 나누어줘야 한다. 

 

컵홀더의 총 개수를 구해보자.

우선 일반좌석 수+커플석좌석 수를 더한 총 좌석수에서 1을 빼준 개수에 

좌석 양쪽 끝에 무조건 2개를 더해주면 구할 수 있다. 

int cup = (cnts + cntl - 1) + 2;

 

마지막으로 컵홀더에 컵을 꽂을 수 있는 사람 수를 출력한다.

만약 컵홀더 개수보다 사람수가 많거나 같으면 컵홀더 개수를 출력, 컵홀더 개수가 더 많으면 사람 수를 출력한다. 

 

코드

#include <iostream>
using namespace std;
/*
1. 좌석수 입력받기
2. 좌석정보 입력받기
3. 컵홀더에 놓을 수 있는 최대사람 수 출력
*/

int main() {
    //1
    int n;
    cin >> n;
    
    //2
    string seat;
    cin >> seat;

    //3
    int cnts = 0, cntl = 0;
    for (int i = 0; i < seat.size(); i++) {
        if (seat[i] == 'S') cnts++;
        else cntl++;
    }

    cntl = cntl / 2; //커플석 반으로 나눠주기
    int cup = (cnts + cntl - 1) + 2;

    //4
    int people = seat.size();
    cout << min(cup, people);
    /* 위의 min함수가 더 빠르지만 이 코드로 해도 됨
    if (cup <= people) cout << cup << '\n';
    else cout << people << '\n';
    */
    return 0;
}

 

느낀 점

그리디 알고리즘인데 어느 부분에서 그리디인지는 잘 모르겠다..^^

커플석과 일반석이 나눠져 있다는 부분을 인지하고

커플석의 경우는 한 좌석으로 생각해줘야 문제가 풀기 쉬웠다.

 

또한 컵홀더는 좌석 양끝에 2개는 무조건 픽스로 가므로

이를 제외한 컵홀더 개수를 구해서 더해주는 식으로 생각하니 편했다.