30013번 - 돌베어 법칙

문제

돌베어 법칙은 아래와 같이 귀뚜라미의 울음소리와 주변 온도의 연관성을 정리한 법칙이다.

• $T = (Count+37),円^{\circ}\mathrm{F}$
• $T$: 기온(화씨), $Count$: 1분 동안 귀뚜라미가 우는 횟수

예찬이는 돌베어 법칙이 진짜인지 증명하기 위해 귀뚜라미가 우는 횟수를 $N$초 동안 직접 측정하려고 한다.

하지만 귀뚜라미 여러 마리의 울음소리가 뒤섞여 제대로 측정할 수 없다는 것을 깨달은 예찬이는 증명을 포기할 수밖에 없었다.

대신 예찬이는 귀뚜라미의 울음소리를 1ドル$초 간격으로 $N$초 동안 측정해 울고 있는 귀뚜라미가 최소 몇 마리인지 알아내려고 한다.

모든 귀뚜라미는 다음과 같은 규칙을 따른다.

• 각 개체는 임의의 시점에 처음 울기 시작한 뒤 주기가 지날 때마다 한 번씩 운다.
• 각 개체가 우는 주기는 임의의 양의 정수이며, 개체에 상관없이 모두 동일하다.
• 각 개체는 임의의 시점에 우는 것을 멈추며, 이후로는 울지 않는다.

예찬이를 도와 현재 울고 있는 귀뚜라미의 최소 개체 수 $X$를 구해보자.

입력

첫째 줄에는 측정 시간 $N$이 주어진다.

둘째 줄에는 예찬이의 측정 기록이 .또는 #로만 구성된 길이 $N$의 문자열로 주어진다.

.은 해당 순간에 귀뚜라미가 울지 않았음을, #은 귀뚜라미가 울었음을 나타낸다.

출력

첫째 줄에 현재 울고 있는 귀뚜라미의 최소 개체 수 $X$를 출력하라.

제한

• 10ドル \leq N \leq 2000$
• 입력으로 주어지는 문자열은 .또는 #로만 이루어져 있다.

힌트