Informatica Online Judge

  The Tower of KOIOI (Large) [0739 / 02E3]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 88   Total Tried : 73


The Champion of this Problem (C++) : gs15120 - 88ms / 1842byte
My Best Submission (C++) : N/A

[]

Background

KOIOI탑이라는 것은 일종의 짝퉁 하노이 버전이다. ^^;

이 게임은 K, O, I 중 하나씩 적힌 원판이 N개가 크기순으로 쌓여있다.

당신은 이들 원판을 사용하여 가능한 많은 미니 KOIOI타워를 만들어야 한다.

KOIOI타워라는 것은 3개의 원판으로 구성되며 원판을 위에서부터 읽었을 때, KOI또는 IOI로 구성된 타워를 말한다. 단, 같은 원판을 2번 이상 사용할 수 없다.

Input

첫 번째 줄에 원판의 수 N이 입력된다. 이 값은 1,000,000이하의 값이다.
두 번째 줄에 타워의 작은 원반부터 큰 원반까지의 길이 N이 입력된다.

Output

만들 수 있는 최대의 미니 KOIOI탑의 수를 출력한다.

IO Example

입력
6
KOIIOI

출력
2

입력2
5
KOIOI

출력2
1

*한 원판을 2번 사용할 수 없기 때문에 1개만 가능

입력3
6
KOIOII

출력3
2

입력4
15
KKOIIOOKOKIOIIO

출력4
4

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]