시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 (추가 시간 없음) | 1024 MB | 371 | 47 | 38 | 33.043% |
원형의 주차 타워가 있다. 주차 타워에는 $N$개의 칸이 원형으로 있다. 각 칸은 시계 방향으로 차례대로 $1$번째, $2$번째, $\dots$, $N$번째 칸으로 부른다. 각 칸에는 차가 한 대씩 들어있다. $i$번째 칸에 있는 차는 번호 $a_i$를 가지고 있다.
주차 타워에는 두 개의 버튼이 있다. 버튼 A를 누르면 주차 타워를 시계방향으로, 버튼 B를 누르면 주차 타워를 반시계방향으로 한 칸 회전할 수 있다. 아래에 있는 왼쪽 그림은 위 예시에서 버튼 A를, 오른쪽 그림은 버튼 B를 누른 다음의 상태를 나타낸다.
이 때, 주차 타워에서 모든 차를 빼려 한다.
맨 아래에 있는 한 개의 칸에서만 차를 뺄 수 있다. 초기 상태에는 $1$번째 칸이 맨 아래에 있다. 맨 아래에 있지 않은 칸에 있는 차를 빼기 위해서는, 먼저 버튼을 적절히 눌러서 주차 타워를 회전해, 차가 있는 칸을 맨 아래로 옮겨야 한다.
추가적으로, 번호 $x$를 가진 차를 빼기 위해서는 먼저 번호가 $x$보다 작은 모든 차를 먼저 빼어야 한다. 즉, 주차 타워에 번호가 $x$ 미만인 차가 남아 있다면, 번호가 $x$인 차를 뺄 수 없다.
주차 타워에서 모든 차를 빼기 위해, 버튼을 눌러야 하는 총 횟수의 최솟값을 구하는 프로그램을 작성하여라.
첫 번째 줄에 정수 $N$이 주어진다.
두 번째 줄에 차들의 번호 $a_1, \dots , a_N$이 순서대로 공백을 사이에 두고 주어진다.
첫 번째 줄에 버튼을 눌러야 하는 총 횟수의 최솟값을 출력하라.
번호 | 배점 | 제한 |
---|---|---|
1 | 8 | $a_i = 1$. ($1 ≤ i ≤ N$), 즉, 모든 자동차의 번호는 $1$이다. |
2 | 9 | $i ≠ j$일 때, $a_i ≠ a_j$. 즉, 모든 자동차의 번호가 다르다. |
3 | 10 | $N ≤ 10$. |
4 | 21 | $N ≤ 100$. |
5 | 31 | $N ≤ 1,000$. |
6 | 21 | 추가 제약 조건 없음. |
4 1 2 2 1
3
차 빼기 → 버튼 A → 차 빼기 → 버튼 A → 차 빼기 → 버튼 A → 차 빼기 순서로 진행하면 된다.
5 3 1 4 5 1
7
Olympiad > 한국정보올림피아드 > KOI 2022 2차대회 > 중등부 3번