| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 557 | 160 | 138 | 30.197% |
여러분, 그거 알아요?
자연에서 태어난 모든 생명들은 바람과 물로 이루어져 햇빛을 받아 이 땅에 존재한다고 해요. 그래서 땅을 보면 우리가 어떻게 살아야 하는지 알 수 있대요.
바람처럼 열린 마음으로 날아오르고 강처럼 쉬지 않고 앞으로 나아가다가 햇빛처럼 괴로운 마음들을 따뜻하게 달래 주고 산처럼 고요히 머무르다 가면 되는 거래요.
-라라 튜토리얼 스토리 중-
메이플스토리의 직업 라라는 용맥 분출이라는 스킬을 이용해 사냥한다.
라라는 해, 강, 바람의 세 종류 용맥을 발견할 수 있는데, 용맥 분출을 사용하면 용맥을 소모하여 해당 위치에 지속적으로 데미지를 주는 토지령이라는 소환수를 소환할 수 있다. 토지령 역시 해, 강, 바람의 세 종류 토지령이 있고, 소모한 용맥과 같은 종류의 토지령이 소환된다. 각 토지령은 종류별로 한 마리씩만 소환할 수 있고, 토지령을 소환할 때 같은 종류의 토지령이 이미 소환되어 있다면 기존에 소환되어 있던 같은 종류의 토지령은 사라지고 종류별로 가장 마지막에 소환된 토지령만이 남는다.
예를 들어 해의 토지령과 강의 토지령이 소환되어 있는 상태에서 용맥 분출로 바람 용맥을 소모했을 경우, 그 위치에 바람의 토지령이 소환된다. 그러나 여기서 해 용맥을 소모했을 경우, 기존에 있던 해의 토지령이 사라지고 새로운 해의 토지령이 소환된다. 강의 토지령과 바람의 토지령은 해의 토지령과는 종류가 다르기 때문에 사라지지 않는다.
용맥 분출에는 한 가지 단점이 있는데, 적절한 종류의 용맥을 소모하지 못한다면 소환했던 토지령이 너무 빠르게 사라져 몬스터에게 충분한 데미지를 주지 못할 수도 있다. 이를 보완하기 위해 라라는 또 다른 스킬인 용맥 변환을 가지고 있다. 용맥 변환을 사용할 때마다 원하는 위치의 용맥 하나를 원하는 다른 종류의 용맥으로 변환할 수 있다.
예를 들어 해 용맥, 해 용맥, 해 용맥이 순서대로 있는 상태에서 두 번째 용맥에 용맥 변환을 사용해 바람 용맥으로 변환할 수 있다. 이 경우 용맥의 배치는 해 용맥, 바람 용맥, 해 용맥이 된다. 이어서 세 번째 용맥에 용맥 변환을 사용해 강 용맥으로 변환할 경우, 용맥의 배치는 해 용맥, 바람 용맥, 강 용맥이 된다.
라라는 $N$개의 용맥이 일렬로 있고, 각 용맥마다 체력이 $H$인 몬스터가 한 마리씩 있는 직선형 맵에서 사냥하려고 한다. 라라는 이 맵의 가장 왼쪽 용맥에서부터 시작하고, 다음과 같은 과정이 반복되어 사냥이 진행된다.
라라는 맵에 있는 모든 몬스터를 처치하기 위해 사냥을 시작하기 전 용맥 변환으로 용맥의 종류를 바꿀 것이다. 단, 용맥 변환은 쿨타임이 있는 스킬이기 때문에 빠른 사냥을 위해 최소한의 횟수로 사용할 것이다.
맵의 모든 몬스터를 처치하면서 용맥 변환을 최소한으로 사용할 때, 그 횟수를 라라에게 알려주자.
첫 번째 줄에는 맵에 있는 용맥의 수와 몬스터의 체력을 나타내는 두 정수 $N,ドル $H$가 공백으로 구분되어 주어진다. $(1 \le N, H \le 1,000円,000円)$
두 번째 줄에는 맵에 있는 용맥의 종류를 순서대로 나타내는 길이 $N$의 공백 없는 문자열이 주어진다.
문자열은 S, R, W로만 이루어져 있고, 각각 용맥의 세 종류인 해, 강, 바람을 나타낸다.
맵의 모든 몬스터를 처치하기 위해 사용해야 하는 용맥 변환 횟수의 최솟값을 출력한다.
만약 아무리 많은 용맥 변환을 사용하더라도 맵의 모든 몬스터를 처치할 수 없다면 대신 -1을 출력한다.
3 4 SRW
0
3 1 SSS
0
3 2 SSS
1
3 3 SSS
2
4 4 SSSS
-1