99클럽 코테 스터디 22일차 TIL: 브루트포스

문제

n이 최대 8이므로, 브루트포스로 풀 수 있는 문제이다.
모든 순열을 구해 가장 많은 던전을 돌 수 있는 횟수를 구하면 된다.

시간복잡도는 $O(n!)$ 으로 예상된다.
예를들어 던전의 개수가 3이라면
123, 132, 213, 231, 312, 321 총 6개 = 3! 이 도출된다.

이는 첫번째 뽑을 수 있는 던전 수 (3), 두번째 뽑을 수 있는 던전의 수는 자기 자신을 제외한 (2) 개 .. 순으로 되기 때문이다.

모든 순열을 구하는 것과 동일하다.

재귀를 통하여 구해주었다.
던전을 선택할 때 현재 피로도가 최소 피로도 보다 많아야 하고, 방문하지 않은 던전이여야 한다.
여기서 백트래킹 기법을 사용했다.

순열 및 조합에 대한 이해 및 백트래킹을 구현할 수 있는 능력이 있다면 어렵지 않게 풀 수 있는 문제였다.