광부들의식사(Miners) > 문제은행

본문 바로가기


문제은행

1068 : 광부들의식사(Miners)

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 14 회    시도횟수: 78 회   



석탄을 캐는 광산이 두 군데 있고 각 광산에는 광부들이 작업을 하고 있다. 채굴 작업은 고된 일이기 때문에 광부에게는 음식을 통한 지속적인 영양 섭취가 필요하다. 매 시각마다 한 음식 세트가 도착하고 이를 공급 받은 광부들은 일정량의 석탄을 생산해 낸다. 음식 세트에는 고기 생선 빵 이렇게 세 종류가 있다.

 

광부들은 다양한 메뉴로 식사를 하고 싶어 하기 때문에 끼니마다 음식 세트가 제각각일수록 작업 생산성이 올라간다. 이를 구체적으로 표현하면 이렇다. 음식 세트가 하나 도착하면 이를 먹고 광부들이 작업을 해서 석탄을 생산하는데 그 생산량은 지금 먹은 음식 세트와 그 전과 그 전전에 먹은 음식 세트(만약 그런 적이 있다면) 이렇게 최대 세 세트를 비교했을 때,

 

단일 메뉴밖에 맛본 적이 없다면 1만큼 석탄을 생산한다.
서로 다른 메뉴로 식사 자체가 두 번째이거나 세 번 중 한 번만 메뉴 중복이 있어서 두 종류의 메뉴를 먹었다면 2만큼 생산한다.
세 세트의 메뉴가 모두 달라서 고기, 생선, 빵을 골고루 맛보았다면 3만큼 석탄을 생산한다.

 

매 시각마다 앞으로 어떤 음식 세트가 순서대로 공급될 것인지 스케줄이 나와 있다. 그 순서 자체를 바꿀 수는 없지만 어떤 음식을 두 광산 중 어디에 보낼지를 적절히 조절함으로써 광부들에게 최대한 균형 잡힌 식단을 제공할 수 있고 이것이 광산 채굴 효율을 극대화할 수 있다. 음식 세트 하나를 둘로 나눌 수는 없으며 어차피 같은 시간엔 음식을 받은 한 광산에서만 작업이 진행된다.

 

두 광산에 균형 잡힌 횟수나 간격으로 음식을 공급해야 할 필요는 없다. 한 광산을 한참 동안 놀리고 있어도 되고, 아예 한 곳에다가만 공급을 올인해도 괜찮다. 오로지 특정 광산에 음식을 공급할 때, 예전과 비교해서 메뉴의 다양성만 보장되면 된다.

 

광산에 공급되는 음식 세트 리스트를 입력 받아, 이를 두 광산에 적당한 순서로 보냈을 때 캘 수 있는 석탄의 최대량을 계산하는 프로그램을 작성하시오.


첫째 줄에는 음식 세트의 총 개수 N (1≤N≤100,000)의 값이 들어있다. 그리고 둘째 줄에는 시간 순으로 공급되는 음식 세트를 의미하는 문자열이 N 글자 들어있다. 문자는 대문자로 M(고기), F(생선), B(빵) 이렇게 셋 중 하나이다.



이 공급 하에서 가능한 석탄의 최대 채굴량을 정수 하나로 출력한다.


[Copy]
6
MBMFFB
[Copy]
12





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.