20311(화학 실험) - 해결

화학 실험

 

문제

화학 실험을 하던 윤이는 일렬로 나열해 놓은 $N$개의 시험관에서 재밌는 특징을 발견했다. 그 특징은 모든 이웃한 시험관 쌍에 대해, 두 시험관에 들어 있는 시약의 색깔이 서로 다르다는 점이었다. 흥미롭다고 느낀 윤이는 실험보고서에 이 사실과 함께 각 색깔별 시약의 수를 적었다. 하지만 보고서를 채점하던 조교 원이는 윤이가 색깔별 시약의 수를 제대로 적었는지 의문이 들었다. 윤이의 보고서와 일치하도록 시험관을 배열할 수 있는지 판별하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 시험관의 개수 $N$과 색깔의 종류 수 $K$가 공백을 사이에 두고 주어진다.

두 번째 줄에 $K$개의 양의 정수 $c_i$가 공백을 사이에 두고 주어진다. 각 색깔에는 번호가 붙어 있으며, $c_i$는 $i$번 색깔의 시약이 담긴 시험관의 개수이다. $(1≤i≤K)$ 

 

출력

조건을 만족하는 시험관 배열을 만들 수 있으면, 시험관의 색깔 번호를 공백으로 구분하여 순서대로 출력한다. 답이 여러 개이면 아무 거나 출력한다.

조건을 만족하는 시험관 배열을 만들 수 없으면 $-1$을 출력한다.

---

처음에는 어떻게 풀어야할지 몰랐는데 

다시 해봤을 때 짝수번째와 홀수번째를 나누어서 정렬했을 때 되는 것을 발견하였다.

import sys
input = sys.stdin.readline

N, K = map(int,input().split())
C = list(map(int,input().split()))

tubes = []

for i in enumerate(C,1):
    tubes.append(i)

tubes.sort(key=lambda x:x[1])

if (N+1)//2 < tubes[-1][1]:
    print(-1)
else:
    tubes_list = []
    for num,cnt in tubes:
        tubes_list += [num] * cnt

    result = [0] * N

    for i in range(0,N,2):
        result[i] = tubes_list.pop()

    for i in range(1,N,2):
        result[i] = tubes_list.pop()

    print(*result)