반응형
1. 문제
2810번 컵홀더
(https://www.acmicpc.net/problem/2810)
십년이면 강산이 변한다.
강산이네 동네에 드디어 극장이 생겼고, 강산이는 극장에 놀러갔다. 매점에서 콜라를 산 뒤, 자리에 앉은 강산이는 큰 혼란에 빠졌다. 양쪽 컵홀더를 이미 옆 사람들이 차지했기 때문에 콜라를 꽂을 컵 홀더가 없었기 때문이다. 영화를 보는 내내 콜라를 손에 들고 있던 강산이는 극장에 다시 왔을 때는 꼭 콜라를 컵 홀더에 놓겠다는 다짐을 한 후 집에 돌아갔다.
극장의 한 줄에는 자리가 N개가 있다. 서로 인접한 좌석 사이에는 컵홀더가 하나씩 있고, 양 끝 좌석에는 컵홀더가 하나씩 더 있다. 또, 이 극장에는 커플석이 있다. 커플석 사이에는 컵홀더가 없다.
극장의 한 줄의 정보가 주어진다. 이때, 이 줄에 사람들이 모두 앉았을 때, 컵홀더에 컵을 꽂을 수 있는 최대 사람의 수를 구하는 프로그램을 작성하시오. 모든 사람은 컵을 한 개만 들고 있고, 자신의 좌석의 양 옆에 있는 컵홀더에만 컵을 꽂을 수 있다.
S는 일반 좌석, L은 커플석을 의미하며, L은 항상 두개씩 쌍으로 주어진다.
어떤 좌석의 배치가 SLLLLSSLL일때, 컵홀더를 *로 표시하면 아래와 같다.
*S*LL*LL*S*S*LL*위의 예에서 적어도 두 명은 컵홀더를 사용할 수 없다.
2. 문제 포인트
- 좌석 종류 2가지 (S석(일반석) L석(커플석))
- 컵홀더는 좌석 사이와 양단 끝에 위치
- 최대 컵홀더 사용 가능 인원 수 구하기
반응형
3. 접근법
- S는 한글자지만 L은 LL두 글자로 표시됨
- 방법 2가지
- L이 두번 반복되는것을 확인 후 L두번당 한번씩 컵 홀더 위치 시키기
- LL을 다른 문자 (ex. C)로 치환하여 풀이
4. 결과 코드_1 (LL의 반복을 확인하여 컵홀더 위치시키기)
import sys
a = int(sys.stdin.readline())
b = sys.stdin.readline()
# 시작점 컵홀더 하나 추가
result = "*"
# 각 자리별 컵홀더 자리 *로 표시
## L이 두번 나오는지 검출하는 방법
for n in b:
# "S"가 나오면 바로 옆에 컵홀더 위치
if n == "S":
result += n + "*"
# 커플석인 L이 나오면 두번 중복되어 나왔는지 확인하여 *추가
if n == "L":
if result[-1] == "L":
result += "L" + "*"
else:
result += "L"
# 결과값 출력
## 일반 좌석만 존재하는 경우 컵홀더 숫자가 좌석수(사람수)보다 1개 많아지는 예외 발생
## min으로 컵홀더 사용 개수가 사람수를 넘어가지 않도록 처리
print(min(result.count("*"), a))
# https://www.acmicpc.net/problem/2810
4. 결과 코드_2 (LL 치환을 이용)
import sys
a = int(sys.stdin.readline())
b = sys.stdin.readline().strip()
# LL(커플석)을 하나의 문자로 치환
b = b.replace("LL", "C")
# 컵홀더 수와 사람수를 비교하여 적은 수 출력
print(min(len(b)+1, a))
# https://www.acmicpc.net/problem/2810반응형
'알고리즘 > 파이썬' 카테고리의 다른 글
| [그리디 알고리즘 Lv.02] 17224번 APC는 왜 서브태스크 대회가 되었을까? (Python) (0) | 2022.09.06 |
|---|---|
| [그리디 알고리즘 Lv.02] 5585번 거스름돈 (Python) (1) | 2022.09.05 |
| [그리디 알고리즘 Lv.02] 2864번 5와 6의 차이 (Python) (0) | 2022.09.02 |
| [그리디 알고리즘 Lv.02] 25496번 장신구 명장 임스 (Python) (0) | 2022.09.01 |
| [그리디 알고리즘 Lv.02] 14655번 욱제는 도박쟁이야!! (Python) (0) | 2022.08.31 |
