[BOJ 24891] 백준 24891번 - 단어 마방진

		2022 숭고한 연합 알고리즘 콘테스트 Open Contest 풀이
A		[BOJ 24883] 자동완성
B		[BOJ 24884] 장작 넣기
C		[BOJ 24885] 주식
D		[BOJ 24886] SKH 문자열
E		[BOJ 24887] 최대한의 휴식
F		[BOJ 24888] 노트 조각
I		[BOJ 24891] 단어 마방진

1. 문제

$24891$. 단어 마방진 (2022 숭고한 연합 알고리즘 콘테스트 I번)

백준 24891번 - 단어 마방진 (https://www.acmicpc.net/problem/24891)

2. 풀이

$L\leq 5,\, N\leq 20$ 이다. 따라서 $20$개 중 $5$개를 고르는 작업이므로, $_{20}C_5=15,504$가지 경우의 수가 있다. 그런데 코드 상으로는 $1$부터 $20$까지 전체를 탐색하므로, $20^5=3,200,000$로 보아야 한다. 어찌됐든 브루트포스로 충분히 탐색이 가능하다.

$L$개의 단어를 고르고 이를 마방진으로 배치한 뒤, 단어 마방진의 조건을 만족하는지 확인하기만 하면 된다. 단, 사전 순으로 가장 빠른 단어 마방진을 출력해야 하므로, 처음에 단어들을 정렬한 뒤에 탐색을 시작한다.

3. 채점 결과

4. 회고

정해진 단어들을 바탕으로 가능한 단어들을 추려내어 시간복잡도를 줄일 수도 있겠다고 생각했지만, 완전탐색이 가능하여 굳이 시도하진 않았던 문제였다.

5. 코드