맨 처음에 길이 1인 배열 [30] 이 주어집니다.
여기에 다음 연산을 원하는 만큼 수행할 수 있습니다.
"배열에 있는 양의 정수 x 를 x - 1 두 개로 만들 수 있다."
가령 [30] 을 [29, 29] 로 만들 수 있고, [29, 29] 에서 오른쪽 29 에 연산을 수행하여 [29, 28, 28] 과 같이 만들 수 있는 것.
연산을 적용하여 숫자를 나눈 뒤 순서를 바꾸면 안됩니다.
가령 [29, 29] 에서 오른쪽 29를 28, 28 로 나누어 위치를 바꾸어 삽입([28, 29, 28] 처럼)하면 안된다는 뜻입니다.
이 때, 우리가 만들 수 있는 배열을 "ZalSequence" 라고 합니다.
예)
[30],
[29, 29],
[28, 28, 29], [29, 28, 28],
[27, 27, 28, 29], [28, 27, 27, 29], ...
길이 N + K 인 "ZalSequence"가 있었는데 K개가 지워진 배열이 주어지면,
K 개를 적절히 추가해서 길이 N + K인 "ZalSequence" 를 만들라는 문제입니다.
<힌트>
더보기
주어진 배열이 "ZalSequence" 인지 확인하는 문제를 먼저 풀면 도움이 됩니다.
주어진 배열이 "ZalSequence" 이려면 무슨 조건을 만족해야 할까요?
중요한 관찰은 연산을 통해 숫자가 쪼개질때 항상 숫자가 2개씩 이웃하여 생성된다는 점입니다.
따라서 배열에서 가장 작은 숫자를 생각해보면 항상 짝을 이루고 있다는 점이 중요한 관찰입니다.