1. 오늘의 학습 키워드
- 그리디
2. 문제: 2810. 컵홀더
- 단계: 🥉 브론즈 1단계
- 주제:
- 출처: https://www.acmicpc.net/problem/2810
문제
십년이면 강산이 변한다.
강산이네 동네에 드디어 극장이 생겼고, 강산이는 극장에 놀러갔다. 매점에서 콜라를 산 뒤, 자리에 앉은 강산이는 큰 혼란에 빠졌다. 양쪽 컵홀더를 이미 옆 사람들이 차지했기 때문에 콜라를 꽂을 컵 홀더가 없었기 때문이다. 영화를 보는 내내 콜라를 손에 들고 있던 강산이는 극장에 다시 왔을 때는 꼭 콜라를 컵 홀더에 놓겠다는 다짐을 한 후 집에 돌아갔다.
극장의 한 줄에는 자리가 N개가 있다. 서로 인접한 좌석 사이에는 컵홀더가 하나씩 있고, 양 끝 좌석에는 컵홀더가 하나씩 더 있다. 또, 이 극장에는 커플석이 있다. 커플석 사이에는 컵홀더가 없다.
극장의 한 줄의 정보가 주어진다. 이때, 이 줄에 사람들이 모두 앉았을 때, 컵홀더에 컵을 꽂을 수 있는 최대 사람의 수를 구하는 프로그램을 작성하시오. 모든 사람은 컵을 한 개만 들고 있고, 자신의 좌석의 양 옆에 있는 컵홀더에만 컵을 꽂을 수 있다.
S는 일반 좌석, L은 커플석을 의미하며, L은 항상 두개씩 쌍으로 주어진다.
어떤 좌석의 배치가 SLLLLSSLL일때, 컵홀더를 *로 표시하면 아래와 같다.
*S*LL*LL*S*S*LL*위의 예에서 적어도 두 명은 컵홀더를 사용할 수 없다.
입력
첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다.
출력
컵을 컵홀더에 놓을 수 있는 최대 사람의 수를 출력한다.
예제 입력 1
3
SSS
예제 출력 1
3
예제 입력 2
4
SLLS
예제 출력 2
4
예제 입력 3
9
SLLLLSSLL
예제 출력 3
73. 문제 풀이
Step1. 문제 이해하기
이 문제는 주어진 좌석 배치에 따라 컵홀더를 최대한 많은 사람이 사용할 수 있도록 계산하는 문제입니다.
주어진 문제의 정보는 다음과 같습니다:
- 서로 인접한 좌석 사이에는 컵홀더가 하나씩 있고, 양 끝 좌석에는 컵홀더가 하나씩 더 있습니다.
- 커플석도 존재하는데 커플석 사이에는 컵홀더가 없습니다.
- 모든 사람은 컵을 한 개만 들고 있고, 자신의 좌석의 양 옆에 있는 컵홀더에만 컵을 꽃을 수 있습니다.
입출력은 다음과 같습니다.
- Input:
- 첫째 줄에 좌석의 수 N이 주어집니다. N은 1이상 50이하입니다.
- 둘째 줄에는 좌석의 정보가 주어집니다.
- Output:
- 컵을 컵홀더에 놓을 수 있는 최대 사람의 수를 출력합니다.
Step2. 문제 분석하기
- 일반 좌석(S):
- 각 좌석마다 컵홀더를 하나씩 사용할 수 있습니다.
- 커플석(L):
- 커플석 두 개가 묶여 있으며, 이 두 좌석 사이에는 컵홀더가 없습니다.
- 커플석 쌍의 양쪽 끝에는 컵홀더가 하나씩 있습니다.
- 컵홀더의 배치 규칙:
- 일반 좌석과 커플석의 배치에 따라 컵홀더의 위치가 결정됩니다.
- 극장의 컵홀더 배치는 항상 좌석의 수보다 많거나 같습니다.
- 양 끝에 컵홀더가 있으므로 시작 시 1개의 컵홀더가 있다고 가정하고 좌석 배열을 처리합니다.
- 최대 사람 수:
- 최대 N명이 앉을 수 있지만, 모든 사람이 컵홀더를 사용할 수는 없습니다.
- 따라서, 실제로 컵홀더를 사용할 수 있는 사람의 수는 N과 실제 배치 가능한 컵홀더 수 중 작은 값입니다.
Step3. 코드 설계
Step4. 코드 구현
import sys
N = int(sys.stdin.readline().strip())
seat = sys.stdin.readline().strip()
def sol(N, seats):
cnt = 0
i = 0
while i < N:
if seats[i] == 'S':
cnt += 1
i += 1
else:
i += 2
cnt += 1
return min(N, cnt + 1)
print(sol(N=N, seats=seat))
- 코드 설계:
- 좌석 탐색:
- 입력받은 좌석 배열을 순차적으로 탐색합니다.
S(일반 좌석)가 나타나면 컵홀더 하나를 사용하고, 다음 좌석으로 이동합니다.L(커플석)이 나타나면 커플석 쌍을 하나의 그룹으로 처리하고, 두 좌석을 건너뛰며 컵홀더 하나를 사용합니다.
- 최대 컵홀더 수 제한:
- 탐색이 끝난 후, 계산된 컵홀더 수와 좌석 수 N 중 작은 값을 반환합니다. 이는 모든 사람이 컵홀더를 사용할 수 없는 경우를 처리하기 위함입니다.
- 시작점의 추가 컵홀더:
- 극장 좌석의 시작점에는 항상 컵홀더가 하나 있으므로, 탐색 과정에서 계산된 컵홀더 수에 1을 추가합니다.
- 좌석 탐색:
- 시간 복잡도:
-
탐색:
- 좌석 배열을 한 번만 탐색하므로 시간 복잡도는 O(N).
-
최종 계산:
- N과 계산된 컵홀더 수 중 작은 값을 반환하는 작업은 O(1).총 시간 복잡도는 이므로 매우 효율적입니다.
-
- 결과:
4. 마무리
이번 문제는 그리디 알고리즘을 사용하여 컵홀더 배치를 효율적으로 처리하는 문제였습니다. 커플석과 일반 좌석의 특징을 반영하여 컵홀더 사용 가능 여부를 계산했고, O(N)의 효율적인 해결책을 구현했습니다. 문제를 간단한 조건으로 나누어 접근하여 구현이 비교적 쉬웠으며, 극장의 좌석 배치와 관련된 직관적인 문제였습니다.
