RiseOJ – 여기가 어디지?

설명

농부 존이 길을 따라 산책을 나갔다가 그만 길을 잃은 것 같다!

길을 따라 $$N$$ 개의 농장( $1 \leq N \leq 100$ )이 일렬로 늘어서 있다. 안타깝게도 농장에는 번지수가 없어서, 농부 존이 길 위에서 자신의 위치를 알아내기가 어렵다. 하지만 각 농장에는 길가에 색깔 있는 우편함이 하나씩 있으므로, 농부 존은 자신에게 가장 가까운 우편함들의 색을 보면 자신이 어디에 있는지 유일하게 알아낼 수 있기를 바라고 있다.

각 우편함의 색은 A..Z 범위의 문자 하나로 표현되므로, 길을 따라 늘어선 $$N$$ 개의 우편함은 A..Z 범위의 문자로 이루어진 길이 $$N$$ 의 문자열로 나타낼 수 있다. 어떤 우편함들은 다른 우편함과 색이 같을 수도 있다. 농부 존은 연속한 $$K$$ 개의 우편함으로 이루어진 어떤 수열을 보더라도 그 수열이 길 위에서 어느 위치에 있는지 유일하게 결정할 수 있게 되는 가장 작은 $$K$$ 값을 알고 싶다.

예를 들어, 길을 따라 늘어선 우편함들의 수열이 'ABCDABC'라고 하자. 농부 존은 $$K=3$$ 으로 정할 수 없다. 'ABC'를 보았을 때, 이 연속한 색 조합이 나타날 수 있는 위치가 길 위에 두 곳 있기 때문이다. 조건을 만족하는 가장 작은 $$K$$ 값은 $$K=4$$ 이다. 연속한 4개의 우편함을 어디에서 보더라도, 이 색 수열이 길 위에서의 위치를 유일하게 결정하기 때문이다.

문제 제공: Brian Dean

제약

문제 제공: Brian Dean

입력 형식

첫째 줄에 $$N$$ 이 주어지고, 둘째 줄에 A..Z 범위의 문자로 이루어진 길이 $$N$$ 의 문자열이 주어진다.

출력 형식

농부 존의 문제를 해결하는 가장 작은 $$K$$ 값을 나타내는 정수 하나를 한 줄에 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 whereami.in · 출력을 쓸 파일 whereami.out

예제 1

입력

7
ABCDABC

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > December > Bronze

올림피아드 > USACO > 2019-2020 > December > Bronze

태그

JudgeUSACO

여기가 어디지?

평가 및 의견

풀이 제출