1248 맞춰봐

최악의 시간복잡도는 총 숫자의 개수 ^ 자릿수 = 16,679,880,978,201개로 시간 안에 해결하지 못한다. 해당 시간복잡도는 조합을 다 만들고 합을 구하는 것이라 시간 복잡도가 매우 크다. 

 

예제를 기준으로 풀이를 설명하면, 해당 연산자는 (x, y)에 대해서 x부터 y까지 합이라고 하면

-+0++++--+

(0, 0)

(0, 1)

(0, 2)

(0, 3)

(1, 1)

(1, 2)

(1, 3)

(2, 2)

(2, 3)

(3, 3)

순으로 만들어진다 

 

하지만 0, 1 ,2 ,3 순으로 만들어지니 해당 조합을 정렬을 하는데 y가 작은 기준으로 한다. 이렇게 돌리면서 하나씩 합을 구하면서, 백트래킹을 할 수 있다 

 

문제: https://www.acmicpc.net/problem/1248

깃허브주소: https://github.com/surinoel/boj/blob/master/1248.cpp