[구현/그리디] 백준 2810 컵홀더 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2810번: 컵홀더

 

 

 

2. 문제 풀이

 컵홀더를 사용할 수 있는 사람의 수를 구하는 문제입니다. 좌석은 S(싱글)과 LL(커플)석이 있습니다. 커플석 사이에는 컵홀더가 없기 때문에, 자칫 컵홀더를 사용하지 못하는 사람이 나올 수 있습니다. (커플이 문제)

 

*S*LL*LL*S*S*LL*

 

 위 예시에서는 2명이 컵홀더를 사용하지 못합니다. 

 

 

2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

[Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

 맨 마지막 사람을 제외하고 모든 사람이 왼쪽 컵홀더만 사용합니다. 그러면 쉽게 부족한 컵홀더를 계산할 수 있습니다.

 

*S*LL*LL*S*S*LL*

 

 그리디 알고리즘적으로 해석하면, 현재 사용할 수 있는 컵홀더를 바로 오른쪽 사람에게 배정하는 방법입니다.

 

 

 

3. 코드

#입력
N = int(input())
seat = input()

cupholder = 1 #컵홀더의 개수 (맨 왼쪽 컵홀더)
for s in seat:
    if s == 'S':
        cupholder += 1
    elif s == 'L':
        cupholder += 0.5

#출력
print(min(N, int(cupholder)))

 가용가능한 컵홀더의 개수를 계산합니다. 맨 왼쪽 컵홀더를 제외하고, S 또는 LL이 와야 오른쪽 컵홀더가 추가됩니다. 즉, S와 LL마다 1개씩 사용할 수 있는 컵홀더가 추가됩니다.

 가용가능한 컵홀더보다 사람 수가 많으면 컵홀더의 개수를 출력하고, 많으면 사람 수를 출력합니다.