백준 #1469 숌 사이 수열

원래 코드

import sys
# sys.stdin = open("input.txt")


def solve(cnt):
    if cnt == 2 * n:
        print(*answer)
        exit()

    for j in range(2 * n):
        if answer[j] == -1:
            for i in range(n):
                if not visited[ls[i]]:
                    if j + ls[i] + 1 < 2 * n and answer[j + ls[i] + 1] == -1:
                        answer[j] = ls[i]
                        answer[j + ls[i] + 1] = ls[i]
                        visited[ls[i]] = True
                        solve(cnt + 2)
                        answer[j] = -1
                        answer[j + ls[i] + 1] = -1
                        visited[ls[i]] = False

n = int(input())
ls = sorted(list(map(int, input().split())))

if ls[-1] + 2 > 2 * n:
    print(-1)
else:
    for i in range(n):
        visited = [False] * 17
        answer = [-1] * (2 * n)
        if ls[i] + 1 < 2 * n:
            answer[0] = ls[i]
            answer[ls[i] + 1] = ls[i]
            visited[ls[i]] = True
            solve(2)

    print(-1)

수정 코드

import sys
sys.stdin = open("input.txt")

def solve(cnt):
    if cnt == 2 * n:
        print(*answer)
        exit()

    if answer[cnt] != -1:
        solve(cnt + 1)
        return

    for i in range(n):
        if not visited[ls[i]]:
            if cnt + ls[i] + 1 < 2 * n and answer[cnt + ls[i] + 1] == -1:
                answer[cnt] = ls[i]
                answer[cnt + ls[i] + 1] = ls[i]
                visited[ls[i]] = True
                solve(cnt + 1)
                answer[cnt] = -1
                answer[cnt + ls[i] + 1] = -1
                visited[ls[i]] = False

n = int(input())
ls = sorted(list(map(int, input().split())))

visited = [False] * 17
answer = [-1] * (2 * n)
solve(0)
print(-1)

풀이

2n 크기의 리스트를 앞에서부터 체크하면서 갖고 있는 숫자를 채울 수 있으면 채우는 방식으로 진행했다.

처음 코드를 짤 때는 for 문으로 전부 체크하면서 진행하였기 때문에 시간이 엄청 오래걸렸다.

맞힌 사람들의 풀이를 보던 도중 나랑 제일 가깝게 풀면서도 시간이 월등히 줄어든 코드를 참고하여 다시 풀어보았다.

백트래킹은 아직도 많이 헷갈린다 ㅠ 더 많이 연습해야겠다.