종이조각1 [Swift][BruteForce] 백준 14391번 (종이 조각) 요구 능력 BruteForce + recursiveFunction(DFS) 문제설명 가로와 세로를 섞어서 찢는데 나올 수 있는 가장 큰 수를 구하는 문제이다. 시간복잡도 종이조각을 가로로 자르거나 세로로 자르는 2가지의 경우가 모든칸에 적용될 수 있으므로 O(2^n)의 시간복잡도를 갖는다. n과 m이 최대4까지 나오니까 2^16이 최악의경우이다. 그리고 가로 혹은 세로로 찢어지는 경우마다 우리는 완전탐색을 해서 한번씩 들여다봐야하기 때문에 O(n *m)의 시간복잡도가 걸린다. 종합적으로 O(2^n * m * n)의 시간복잡도가 걸리는것이다. DFS() 처음에는 이게 무슨뜻이지 싶었는데, 방문처리가 true로 처리됬을 경우에는 가로로 찢어진것을 의미하고, 방문처리가 false로 처리됬을 경우에는 세로로 찢.. 2022. 3. 22. 이전 1 다음