백준 알고리즘 2810: 컵홀더 (Python)

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

2810번: 컵홀더

---

문제 해결을 위한 과정

이 문제는 그리디 알고리즘으로 쉽게 해결할 수 있는 문제였습니다. 먼저 그림과 함께 예시를 보도록 하겠습니다.

1) 일반적인 경우

예시를 그림으로 표현하면 위의 그림과 같은데 먼저 좌측부터 채워나간다고 하겠습니다. 이렇게 하면 마지막 커플석의 경우 좌측 우측 컵홀더를 이용할 수 있고 사용하지 못하는 사람은 2번째 커플석에서 1명, 3번째 커플석에서 1명

총 2명이 됩니다. 이를 확장하면 존재하는 커플석 -1 의 사람 수만큼 컵홀더를 사용할 수 없습니다. 따라서 입력받은 컵홀더의 수 - 1이 정답이 됩니다.

 

2) 예외의 경우

예외의 경우가 한가지 존재하는데 바로 전체다 S인 경우입니다. 이 경우는 커플석이 존재하지 않으므로 위의 

커플석 - 1로는 해결 할 수 없습니다. 이 경우는 일반 좌석의 개수보다 컵홀더가 하나 더 많기 때문에 일반석 모두 컵홀더를 사용할 수 있습니다. 따라서 이 경우 입력받은 S의 수를 그대로 출력합니다.

---

소스코드

n = int(input())
data = input()
count = 0
for i in range(len(data)):
  if data[i] == 'L':  
    count += 1
 
if count == 0: # 커플석이 없는 경우
  print(n)
else:
  print(n-(count//2-1))