[BOJ 2810 // C++] 컵홀더

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2810번 문제인 컵홀더이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2810

2810번: 컵홀더

 

문제 상황에 대한 간단한 관찰을 해보자. 컵홀더가 좌석의 수보다 많은 경우를 제외한다면(모든 좌석이 S인 경우), 가장 많은 개수의 컵홀더를 사용했지만 빈 컵홀더가 남아있는 경우가 존재할 수 있을까?

 

그러한 경우는 존재하지 않는다. 그 증명은 항상 모든 컵홀더를 사용할 수 있는 방법이 있다는 것을 보이는 방식으로 할 수 있다.

 

컵홀더의 개수가 좌석의 수 이하이면 LL 좌석이 최소 한번은 등장할 수밖에 없다. 처음 등장하는 LL을 기준으로 1) 왼쪽에 존재하는 컵홀더는 그 컵홀더의 오른쪽에 있는 좌석의 사람이, 2) 오른쪽에 존재하는 컵홀더는 그 컵홀더의 왼쪽에 있는 좌석의 사람이 사용하는 경우, 주어진 좌석에 설치된 모든 컵홀더를 이용할 수 있다.

 

따라서, 이 문제는 (모든 좌석이 S인 경우를 빼면) 주어진 좌석정보를 보고 컵홀더의 개수를 세는 문제로 바꿔 생각할 수 있다. 이는 전체 N+1개의 컵홀더(모든 좌석이 S인 경우) 가운데 LL의 좌석배치로 인해 놓을 수 없게 된 컵홀더 1개를 제외하는 방식으로 계산할 수 있다.

 

예제에서 보이듯, SLLLLS와 같은 배치에서 두 커플석 LL과 LL 사이에는 컵홀더가 있음에 유의하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int main()
{
    int N; string s; cin >> N >> s;
    
    int ans = N + 1;
    int cnt = 0;
    for (int i = 0;i < N;i++) {
        if (s[i] == 'L') {
            ans--;
            i++; // 커플석 하나는 LL의 배치를 가지고 있으므로 문자를 두 개 건너뛰기 위함
        }
    }

    if (ans > N) ans = N; // 모든 좌석이 S인 경우
    cout << ans;
}