12905번 - 거짓말쟁이

BOJ 알고리즘 캠프에 참가한 사람 N명이 교실의 앞에 모여서 원형으로 앉아있다. 각 사람은 반시계 방향으로 0번부터 N-1번까지 번호가 매겨져 있다.

캠프에 참가한 모든 사람은 정직한 사람이거나 거짓말쟁이이다. 정직한 사람은 항상 사실만을 말하고, 거짓말쟁이는 항상 거짓만을 말한다.

백준이는 사람들에게 오른쪽에 앉아있는 사람이 거짓말쟁이인지 묻는 질문을 했다. 정직한 사람은 정직하게 거짓말쟁이는 거짓말로 대답을 한다. 정직한 사람과 거짓말쟁이 모두 답변을 거부할 수도 있다.

사람들의 대답이 주어졌을 때, 그러한 대답이 나오는 정직한 사람과 거짓말쟁이의 조합이 존재하면, 거짓말쟁이 수의 최솟값을, 가능한 조합이 없으면 -1을 출력하는 프로그램을 작성하시오.

첫째 줄에 사람의 수 N이 주어진다. (2 ≤ N ≤ 50)

둘째 줄에는 사람들의 답변이 주어진다.

답변이 L인 경우에는 거짓말쟁이라고, H인 경우에는 정직한 사람이라고 대답한 것이고, ?인 경우에는 답변을 거부한 것이다.

입력으로 주어진 대답이 나오는 정직한 사람과 거짓말쟁이의 조합이 존재하면, 거짓말쟁이 수의 최솟값을, 가능한 조합이 없으면 -1을 출력한다.

예제 1은 다음과 같다.

• 사람 1은 사람 2가 거짓말쟁이라고 했다.
• 사람 2는 사람 3이 거짓말쟁이라고 했다.
• 사람 3은 사람 1이 정직한 사람이라고 했다.

모든 사람이 정직한 사람인 경우는 존재하지 않는다. 만약, 사람 2가 거짓말쟁이이고, 나머지 사람이 정직한 사람이라면 위와 같은 답변이 나올 수 있다.

예제 3의 경우에 사람 2와 사람 3이 거짓말쟁인 경우가 가능하다.