[일반] 재미있는 문제 하나 갖고옴

[익명(175.223)]

왼쪽에 있는 칩을 사용해서 오른쪽에 있는 판내부를 완벽하게 채우는 모든 경우의수를 구하는 방법

완탐보다 좋은방법이 있을까?

문제 이해안되면 댓글로 물어보셈

[익명(1.252)]

ㄷㄷ 소오오전

[ㅇㅅㅌ.(woemtis)]

이게몬대십덕아

[익명(175.223)]

글에 빼먹었는데 왼쪽에 있는 칩은 90도 간격으로 회전이 가능

[dd(180.71)]

일단 왼쪽에 있는 칩을 배열에 상대좌표로 저장을 해놓고 빈칸에 왼쪽 위부터 채워나가는 식으로 백트래킹 하면서 완탐할 듯. 한 번 두면 다음 재귀를 부를 때는 어디서부터 둬야하는지 좌표만 주고 재귀 내부에서는 둘 수 있는지 여부만 체크하고 둘 수 있으면 board값 채워넣고 백트래킹시 board값 다시 빼내고... 오른쪽 맨밑 다 와갈시 board가 꽉찼는지 확인해주고... 꽉찼으면 return 1

[익명(218.54)]

NP-완전 느낌인데 완탐 말고 답 업슬듯

[익명(49.167)]

애초에 모든 경우를 탐색바라는데 완탐은 필연적이지 않나..