5431번 - 책 쌓기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 315 | 74 | 62 | 38.750% |
문제
선영이는 다양한 크기의 책을 쌓아서 스택 형태로 보관한다. 이런 스택의 가장 위에서부터 크기가 감소하지 않는 순서로 책이 쌓여져 있다면, 스택이 안정된 상태라고 한다. 그렇지 않은 경우에는 스택이 무너질 수도 있다.
선영이는 책이 무너지는 것을 막기 위해서 크기 순으로 스택을 정렬하려고 한다. 선영이는 스택의 중간 (또는 바닥)에서 책을 하나 뺀 다음, 가장 위에 놓는다. 하지만, 빼려고 하는 책의 위에 있는 스택이 안정된 상태이어야 한다.
아래 그림은 3, 4, 1, 2로 쌓여진 책을 크기 순으로 정렬하는 방법이다.
현재 책이 쌓여져 있는 상태가 입력으로 주어졌을 때, 안정된 상태로 책을 쌓기 위해 최소 몇 단계가 필요한지 구하는 프로그램을 작성하시오. 위의 그림의 경우에 답은 3이다.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100보다 작거나 같다.
각 테스트 케이스의 첫째 줄에는 책의 수 n이 주어진다. (1 ≤ n ≤ 50) 다음 줄에는 책의 크기 si가 스택의 맨 위에서부터 순서대로 주어진다. (1 ≤ si ≤ 1000)
출력
각 테스트 케이스에 대해서, 필요한 단계의 수의 최솟값을 출력한다.
예제 입력 1
4 4 3 4 1 2 8 3 1 4 1 5 9 2 6 5 1 42 42 42 1000 22 4 1 2 5 6 7 9 10 3 13 17 11 12 14 19 20 22 8 15 16 18 21
예제 출력 1
3 53 0 1234567
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2012 J번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호