목걸이와 팔찌 서브태스크 5초 512MB
문제
동현이는 1~K 중 하나의 색깔을 가진 N개의 구슬들로 목걸이를 만들었다.
i번째 구슬은 i+1번과 i-1번 구슬에 인접해있다. (1번은 N번과 연결되어있다.)
동현이는 목걸이가 마음에 들지 않아서 목걸이를 두 개로 잘라 팔찌를 만들기로 결심했다.
동현이는 목걸이에서 구슬과 구슬 사이를 정확히 두 번 잘라서 두 부분으로 쪼갤 것이다. (잘라진 두 부분 모두 구슬이 적어도 하나는 있어야 한다.)
예쁜 팔찌를 만들기 위해서는 이렇게 구슬들을 나누었을 때 한 종류의 색깔이 한 쪽 팔찌에만 온전히 포함되어야 한다.
또한 팔찌 두 개의 길이 차이가 너무 심하면 안 되므로 쪼개진 두 부분의 구슬 개수의 차이를 최소화하고 싶다.
입력
첫 줄에 N, K가 주어진다. (1 <= K <= N <= 1 000 000)
두 번째 줄에 N개의 수가 주어지며 i번째 수는 i번째 구슬의 색깔을 의미한다. (1 <= 구슬의 색 <= K)
주어지는 목걸이는 적어도 하나 이상의 방법으로 올바르게 분할할 수 있다.
<서브태스크>
#1 (40점) : N <= 1000
#2 (60점) : 추가적인 제한 조건이 없다.
출력
주어진 목걸이를 예쁜 팔찌로 올바르게 분할하는 방법의 수와 그런 방법 중 두 부분의 구슬 개수 차이의 최솟값을 공백을 사이에 두고 출력하라.
예제
9 5
2 5 3 2 2 4 1 1 3
4 3
로그인해야 코드를 작성할 수 있어요.