www.acmicpc.net/problem/2810

 

2810번: 컵홀더

첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다.

www.acmicpc.net


문제 설명

SLLS와 같이 문제가 주어진다.

- S는 *S*로 표현된다.

- LL은 항상 한 쌍으로 주어지며, *LL*로 표현된다.

즉, 예제인 SLLS는 *S*LL*S*로 이해하면 된다.

 

이 때, *는 컵홀더를 의미하고, S 또는 L은 사람을 의미한다.

 

S와 L은 본인 옆에 있는 컵홀더를 한 개씩 사용할 수 있다.

이 때, 최대 몇 명이 컵홀더를 사용할 수 있는지를 출력하면 된다.

 

위 예제의 이 경우 4명이 사용할 수 있다.

문제 분석

 

왼쪽 필기에 대한 설명으로는,

1. 다양한 경우의 수를 통해 예제를 만들어 보았다.

2. 이 때, 최대의 인원이 컵 홀더를 사용할 수 있도록 매칭시켰다.

3. 오른쪽에 3/3과 같이 적은 숫자는 컵홀더를 사용한 사람/ 총 사람의 수를 의미한다.

 

결론적으로,

"총 인원 >= 컵홀더 수" 일 때, 컵홀더의 수가 정답으로 출력된 것을 알 수 있었다.

반대로 "총 인원 < 컵홀더의 수"인 경우에는 "총 인원의 수"가 정답으로 출력된다.

 

 

알고리즘 구상

문제 분석에서 총 인원컵 홀더의 수만 알면 정답을 낼 수 있었다.

 

1. 총 인원은 첫 번째 INPUT에서 주어진다.

2. 컵 홀더(*)의 수를 구해보자.

 - 예제로 SLLS 가 있다고 가정하자.  컵 홀더는 *S*LL*S*와 같이 배치되어야 한다.

 - 이 때, LL을 한 사람으로 보고 *S*L*S*과 같이 표현할 수 있다. (replace 함수 적용)

 - *S*L*S*를 살펴보면, 컵 홀더의 갯수SLS 의 총 길이보다 1 만큼 더 많은 것을 발견할 수 있다.

3. 컵 홀더와 총 인원을 비교

코드

import sys
nPeople = int(input())
seats = input().replace('LL', 'L')
nCups = len(seats) + 1
People >= nCups:
    print(nCups)
else:
    print(nPeople)

 

+ Recent posts