17136 색종이 붙이기
-
백준 17136 색종이 붙이기Algorithm/BOJ 2021. 3. 28. 19:14
출처: www.acmicpc.net/problem/17136 분류: 완전탐색 접근방식 가능한 색종이를 열심히 붙이면 되는 문제였습니다. 처음엔 크기가 5x5인 색종이부터 먼저 붙여나가는 방식으로 접근했는데 이렇게 되면 틀리더라구요.. 반례가 있나봅니다. 따라서 백트래킹으로 모든 경우를 찾아주는 방식으로 접근해야 합니다!! 그리고 이것도 단순히 크기가 1인 색종이부터 확인해나가면 모두 1인 칸일 경우에는 엄청난 연산이 필요하게됩니다. 크기 5부터 접근해서 찾고, 이미 찾은 최소 케이스보다 많이 사용하게되면 그 이상은 무의미하니 거기서 중단해주면 시간을 단축시킬 수 있습니다. 나머지는 단순 구현이라 코드를 보시면 어렵지않게 이해가 되실 것 같습니다 :) 해결방법 func solution() { typeali..