[Python/파이썬] 백준 1469번 숌 사이 수열

https://www.acmicpc.net/problem/1469

 

코드

from copy import deepcopy

n = int(input())
x = sorted(list(map(int, input().split())))
answer = []
arr = [-1]*(2*n)


def bt(idx):
    if idx == n:
        new_arr = deepcopy(arr)
        answer.append(new_arr)
        return
    for i in range(2*n-x[idx]-1):
        if arr[i] == -1 and arr[i+x[idx]+1] == -1:
            arr[i] = x[idx]
            arr[i+x[idx]+1] = x[idx]
            bt(idx+1)
            arr[i] = -1
            arr[i+x[idx]+1] = -1


bt(0)
if len(answer) == 0:
    print(-1)
else:
    answer.sort()
    print(*answer[0])

 

💡 문제 & 해결

처음에는 arr을 다른 배열로 깊은 복사하지 않고 그대로 answer에 넣었다가 출력이 "-1 -1 -1 -1 -1 -1"이 나왔다. 이는 arr이 계속 값이 변하기 때문이다. arr을 깊은 복사로 아예 메모리 주소가 다른 배열로 복사해서 넣지 않고 answer에 arr을 그냥 append한다면 arr의 값이 변할 때마다 answer 안의 배열의 값들도 계속 변한다.

 

그래서 그 다음에는 arr에 숫자가 아닌 문자로 넣은 후에 answer에 append할 때 문자열로 변환해서 넣었는데, 이렇게 했더니 정렬할 때 문제가 발생했다. 문자로 정렬한다면 10이 2보다 앞에 오게 된다. 

 

그래서 그냥 다시 arr에 숫자로 넣도록 한 뒤에 idx==n이 되면 그때의 arr 값을 깊은 복사하여 answer에 append하도록 바꿨다. 이렇게 하면 answer에 들어가게 되는 배열들이 모두 다른 메모리 주소를 갖기 때문에 arr의 값을 수정해도 answer의 원소로 있는 배열들의 값은 영향이 없다.