지그재그 탑 쌓기
실버 V의견: 0
마법사 수아는 마법 탑을 \(N\)층으로 쌓으려 한다. \(N\)개의 블록이 있으며, 각 블록의 무게는 서로 다른 양의 정수이다. 탑이 안정적으로 서려면 블록의 무게 수열이 지그재그여야 한다: 홀수 번째(1번째, 3번째, …) 위치의 블록이 인접한 블록보다 더 가볍고, 짝수 번째(2번째, 4번째, …) 위치의 블록이 인접한 블록보다 더 무거워야 한다.
즉, 아래 조건을 만족해야 한다.
$$ a_1 < a_2 > a_3 < a_4 > a_5 < \cdots $$
주어진 \(N\)개의 블록을 이 조건을 만족하도록 배열하여라. 가능한 답이 여러 가지이면 아무 것이나 출력한다.
- \(1 \le N \le 100\,000\)
- 블록의 무게는 서로 다른 양의 정수이며, 각 무게는 \(10^9\) 이하이다.
첫째 줄에 블록의 수 \(N\)이 주어진다.
둘째 줄에 블록의 무게 \(N\)개가 공백으로 구분되어 주어진다. 모든 무게는 서로 다르다.
지그재그 조건을 만족하는 블록의 배열을 공백으로 구분해 한 줄에 출력한다. 가능한 답이 여러 가지이면 아무 것이나 출력한다.
3
3 1 2
1 3 2
정렬하면 \(1, 2, 3\)이다. 위치 \((1,2)\)를 교환하면 \(1, 3, 2\)가 되어 \(1 < 3 > 2\)를 만족한다. (다른 답도 가능)
5
5 1 3 2 4
1 3 2 5 4
정렬 후 \(1, 2, 3, 4, 5\). 위치 \((1,2)\)와 \((3,4)\)를 교환하면 \(1, 3, 2, 5, 4\). 이 수열은 \(1 < 3 > 2 < 5 > 4\)를 만족한다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
지그재그 탑 쌓기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
지그재그 탑 쌓기