Informatica Online Judge

  마트료시카 [2296 / 08F8]

Time Limit(Test case) : 5000(ms)
Number of users who solved : 0   Total Tried : 0


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[ACM ICPC 2013 WF]

Background

마트료시카 인형은 그 안에 더 작은 인형을 겹쳐 넣는 러시아 전통 나무 인형이다. 인형을 한 겹 벗겨내면 그 안에 같은 종류의 인형이 있고, 또 벗겨내면 그 안에 인형이 또 있고...



러시아 마트료시카 인형 박물관에서는, 그 안에 겹쳐넣을 수 있는 개수가 다른 비슷한 디자인의 마트료시카 세트들을 전시 중이다. 하지만, 마트료시카 인형을 너무 너무 재미있어하는 어떤 꼬마 아이가 다른 사람들이 보지 않을 때, 여러 개의 마트료시카 인형들을 모두 뽑아 섞어 한 줄로 펼쳐놓아 버렸다.

마트료시카 인형들을 다시 모아 넣어야 하는데, 정수 크기의 n개의 인형들이 한 줄로 놓여있다. 원래 처음에 있었던 마트료시카 인형 세트가 몇 개였는지도 모르고, 그 안에 몇 개씩 들어있었는지도 모른다. 하지만 다행히도, 각각의 인형들은 1개부터 m까지 빠짐없는 크기로 포개어 겹쳐져 있었다는 정보는 알고 있다.

마트료시카 인형 세트들을 원래대로 만들기 위해서 다음과 같은 규칙을 따라야 한다.:
- 더 작은 인형이나 인형세트를 크기가 더 큰 인형 안에 겹쳐 넣을 수 있다.
- 한 줄로 늘어서있는 바로 옆의 인형들끼리만 겹쳐 넣을 수 있다.
- 일단 인형을 겹쳐 넣고 나면, 빼내서 다른 인형으로 이동시킬 수 없고 그 인형세트에서 빼낼 수도 없다. 인형세트 2개를 서로 합칠 때에만 임시로 분리시킬 수 있다.

작업시간을 최대한 빠르게 하고 싶은데, 인형을 열고 닫는 데에만 시간이 든다. 예를 들어, 크기가 [1, 2, 6] 으로 겹쳐진 인형세트와 [4] 인형을 합치는데 필요한 시간은 2이다. 크기가 6인 인형과 4인 인형을 분리했다가 합쳐야하기 때문이다. [1, 2, 5] 세트와 [3, 4] 세트를 합치는데 필요한 시간은 3이다.

한 줄로 펼쳐놓은 마트료시카 인형 세트들을 합치는데 필요한 최소 시간을 계산해보자.

Input

첫 번째 줄에는 한 줄로 늘어서 있는 인형들의 개수(n)가 입력된다. (1<=n<=500)

두 번째 줄에는 각 인형들의 크기(si)가 공백을 두고 순서대로 입력된다. (1<=si<=500)

Output

마트료시카 인형들을 합치는데 필요한 인형 분리 횟수의 최솟값을 출력한다. 인형들을 원래 상태로 만들지 못할 경우 impossible을 출력한다.(꼬마 아이가 인형 몇 개를 가져가서 원래 상태로 못 만들 수도 있다.)

IO Example

입력1
7
1 2 1 2 4 3 3

출력1
impossible

입력2
7
1 2 3 2 4 1 3

출력2
7

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