[BOJ 2810, C++] 컵홀더

그리디 레벨이 엄청 낮길래 DP처럼 브론즈부터 플레5까지 풀기로 결정하였다.

 

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

2810번: 컵홀더

 

풀이

컵홀더를 되도록이면 왼쪽에 있는 컵홀더를 사용하는 것이 최적해이다.

컵홀더는 왼쪽 아니면 오른쪽만 사용할 수 있으니 for문을 사용하여 순서대로 좌석을 확인하면 i번째 좌석 차례엔 무조건 오른쪽 컵홀더는 비어있다는 것이 보장이 된다.

그래서 왼쪽 컵홀더가 비어있는지 확인하여 왼쪽 컵홀더 우선순위로 컵홀더를 사용하면 된다.

이때 커플석인 경우에 왼쪽 L이 왼쪽 컵홀더를 사용하지 못할 경우 아예 사용하지 못하니 이 점을 주의하면 된다.

 

1. S일 때

오른쪽 컵홀더 자리가 무조건 비어있다는 것을 알고 있으니 (사용할 수 있는 사람 수) += 1을 해주면 된다.

 

2. LL일 때

왼쪽 L을 기준으로 왼쪽에 컵홀더가 있으면  (사용할 수 있는 사람 수) += 2 이지만 왼쪽에 컵홀더가 없으면 오른쪽 L만 오른쪽 컵홀더를 사용할 수 있으므로 (사용할 수 있는 사람 수) += 1이다.

 

코드는 위의 방법으로 커플석을 한 번에 처리하였다.

 

코드

x = 현재 컵홀더의 위치, ans = 컵홀더 이용자의 수, i = i번째 사람

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
using ll = long long;
 
const int N = 52;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    string s;
 
    cin >> n;
    cin >> s;
 
    int x = 0, ans = 0;
    for (int i = 0; i < n;) {
        if (x > n) break;
        if (s[i] == 'S') {
            x++; ans++; i++;
        }
        if (s[i] == 'L') {
            if (x == i) {
                x += 3; ans += 2;
            }
            else{
                x += 2; ans++;
            }
            i += 2;
        }
    }
 
    cout << ans << endl;
 
}