[백준][백트래킹] 1248번 맞춰봐

문제

개수 N이 주어지고 가능한 모든 N*(N+1)/2개의 구간의 합에 대한 부호가 주어질 때, 수열 N을 구하시오.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1248)

풀이

처음에 어렵다고 느껴서 헤맸던 문제입니다! N이라는 숫자가 주어지고 구간의 합의 모든 조합에 대한 +, -, 0가 주어질 때 이 모든 조건을 만족하는 수열을 구해야합니다. 처음에는 입력을 1차원 배열로 받다보니 i번째 자신에 대한 부호를 찾는 것도 몇번째에 위치하고 있는지 계산을 해야해서 복잡해졌습니다. 그래서 이 방법을 처음에 시도했다가 배열을 N*N으로 만들어서 첫째 줄에서는 N개를 사용, 두번째 줄에는 N-1개를 사용하도록 했습니다. 그렇게 하니 i번째 자리의 부호를 알기 위해서는 number[i][0] 에 자신의 부호가 있으므로 바로 확인할 수 있었습니다. 첫째자리부터 부호에 따라 숫자를 채워가고, 가능하다면 계속해서 둘째자리, .. , N번째자리까지 채워갑니다. i번째 숫자를 정했을 때 확인해야하는 합의 부호는 i개 입니다. 왜냐면 i-1번째까지는 가능한 모든 조합이 옳아서 i번째를 결정할 수 있는 것이므로 첫번째 숫자에서부터 i번째의 합까지, 두번째 숫자에서 i번째의 합까지! 계속해서 i번째 숫자에서 i번째 숫자의 합까지(자신의 부호) 확인합니다. 2차원 배열에서 살펴보면 자신의 부호를 확인하는 number[i][0] 에서 대각선을 타고 내려감을 알 수 있습니다. 

백트래킹 문제이기때문에 위의 방법으로 promising 한지를 확인해주며 각 자리의 부호에 맞게 숫자를 정해주고 조건을 만족하지않으면 다시 돌아가서 새로운 숫자를 정해주며 반복하게 되면 N개의 수열이 완성됩니다! 

여러개의 수열이 나올 수 있으므로 한번 결과가 나오면 해당 결과를 출력하고 끝내면 됩니다. 저는 한번 결과가 나왔을 경우 found = 1 을 해주어서 백트래킹 함수의 첫번째에서 더이상 반복되지 않도록 해주었는데, 이미 N-1번째까지 반복된 경우에는 계속 출력이 되는 경우가 생겨서 틀렸습니다를 2번 받았습니다.(ㅠㅠ) promising 함수에도 found = 1 일경우에는 가지치기를 통해 숫자를 더 이상 채우지 않도록 해주어서 맞았습니다!

코드

https://github.com/kswim/Algorithm/blob/master/Backtracking/1248.cpp