백준 1096번: 종이 접기

주어진 종이를 여러 번 적당히 잘 접어서 만들 수 있는 가장 큰 수를 찾는 문제이다.

접어서 같은 위치에 겹치게 되는 숫자는 합해주면 된다.

 

N과 M이 12 이하이므로, 완전 탐색 문제라는 것은 어렵지 않게 알 수 있다.

다만 완전 탐색 치고 생각보다 까다롭다.

가로를 접는 경우의 수와 세로를 접는 경우의 수는 순서로 따지면 각각 넉넉잡아 11!개 정도이고, (실제로는 7만 4000개 정도이다), 겹쳐진 상태만 고려한다고 해도 $2^{12}$ 가지이다. 둘을 곱해주면 $2^{24}$ 정도로 시간초과나기 딱 좋은 수치이다.

 

약간 관찰을 해 보면 겹쳐진 상태가 $2^{12}$가지 보다는 훨씬 더 적다는 것을 알 수 있다. 예컨대 길이 4개짜리를 접어서, 1, 3, 4번만 겹치도록 만드는 것은 불가능하다.

 

그렇다면 $2^{12}$가지 중 가능한 경우는 몇 가지일까? 어떠한 경우가 가능한 경우인지는 쉽게 알기 힘들지만, 완전탐색을 해 보면 이를 알 수 있다. (길이 12일 때 가능한 경우는 435가지이다)

마찬가지로 세로 길이에 대해서도 가능한 경우를 완전 탐색한다.

 

두 번의 완전 탐색이 끝나면 가로와 세로 각각의 모든 가능한 상태에 대해 다시 한 번 완전탐색을 하면 된다. 각각 예상보다 훨씬 더 적은 435가지 정도의 상태만 존재하므로, 완전탐색은 금방 끝난다.

 

어찌보면 간단한 문제일 수도 있지만, 완전탐색에 접근하는 방법이 다소 특이한 면이 있어 대회에서 만난다면 당황할지도 모르겠다.

 

1096.cpp