[BOJ] 12094번: 2048

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

Backtracking으로 열심히 구현만 하면 됩니다. 12100번의 2048 easy의 경우에는 최적화를 신경 안쓰고 짜면 되는데, 10단계를 들어가는 hard의 경우에는 최적화를 군데군데에서 해주어야 합니다. 저는

1. ans가 그 board에서 기대할 수 있는 최댓값에 도달했을 경우 더 이상 들어가지 않음.(예를 들어 board의 수의 합이 12인데 ans가 현재 8이라면 더 커질 가능성이 없음)

2. 앞으로 계속 2배씩 증가해도 ans를 넘을 수 없을 경우 더 이상 들어가지 않음.

3. board의 변화가 없을 경우 더 이상 들어가지 않음.

4. board에서 수의 갯수의 변화가 없을 경우 다음 depth로 갈 때 그 방향은 제외함

이 4가지 최적화를 했습니다. 재귀의 특성상 디버깅이 굉장히 어려워 고생했네요.

https://github.com/blisstoner/BOJ/blob/master/12094.cpp