https://www.acmicpc.net/problem/2810
2810번: 컵홀더
첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다.
www.acmicpc.net
문제 해결을 위한 과정
이 문제는 그리디 알고리즘으로 쉽게 해결할 수 있는 문제였습니다. 먼저 그림과 함께 예시를 보도록 하겠습니다.
1) 일반적인 경우
예시를 그림으로 표현하면 위의 그림과 같은데 먼저 좌측부터 채워나간다고 하겠습니다. 이렇게 하면 마지막 커플석의 경우 좌측 우측 컵홀더를 이용할 수 있고 사용하지 못하는 사람은 2번째 커플석에서 1명, 3번째 커플석에서 1명
총 2명이 됩니다. 이를 확장하면 존재하는 커플석 -1 의 사람 수만큼 컵홀더를 사용할 수 없습니다. 따라서 입력받은 컵홀더의 수 - 1이 정답이 됩니다.
2) 예외의 경우
예외의 경우가 한가지 존재하는데 바로 전체다 S인 경우입니다. 이 경우는 커플석이 존재하지 않으므로 위의
커플석 - 1로는 해결 할 수 없습니다. 이 경우는 일반 좌석의 개수보다 컵홀더가 하나 더 많기 때문에 일반석 모두 컵홀더를 사용할 수 있습니다. 따라서 이 경우 입력받은 S의 수를 그대로 출력합니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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))
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 2178: 미로 탐색 (Python) (0) | 2021.01.19 |
|---|---|
| 백준 알고리즘 1260: DFS와 BFS (Python) (0) | 2021.01.19 |
| 백준 알고리즘 13305: 주유소(Python) (0) | 2021.01.19 |
| 백준 알고리즘 1715: 카드 정렬하기 (Python) (0) | 2021.01.11 |
| 백준 알고리즘 2437: 저울 (Python) (0) | 2021.01.03 |