[파이썬] BOJ_2810(컵홀더)

 

 

문제

 

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

2810번: 컵홀더

---

 

해설

반응형

 

SLLLLSSLL을 나눠서 보면

S / LL / LL / S / S / LL로 나눌 수 있다. S는 한 좌석에 컵홀더 1개, L은 두 좌석에 컵홀더 1개.

그렇다면 * / S* / LL* / LL* / S* / S* / LL* 로 표현할 수 있다.

결국 S는 1개당 컵홀더 1개 더해주면 되고, L은 L//2개당 컵홀더 1개를 더해주면 된다.

가장 왼쪽의 첫번째 컵홀더도 빼먹으면 안된다.

 

총 컵홀더의 개수를 구하고 나면 컵홀더와 사람 수 둘 중 작은 값을 출력해주면 된다.

문제에서 물어보는 것이 컵홀더에 컵을 놓을 수 있는 최대 사람의 수를 구하는 것이기 때문이다.

문제의 예시처럼 SSS인 경우는
* / S* / S* / S*로 사람은 3, 컵홀더는 4이므로 컵을 놓을 수 있는 최대 사람의 수는 3이 되기 때문이다.

---

코드

 

-파이썬

#백준 2810(컵홀더)

n = int(input())
seat = list(input())
cup = 1  #가장 왼쪽 컵홀더 +1

# */S*/LL*/LL*/S*/S*/LL*/
cup = cup + seat.count("S") + (seat.count("L") // 2)
print(min(cup, n))