7-N 시간 복잡도 접근 질문드립니다.

Question

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 단순히 한 자리에서 5번 호출, 영향을 받을 수 있는 지점 99개가 있으므로 최대 약 5^99 이라고 생각했거든요. 5x5의 색종이를 붙이니까 영향 받는 타일이 더 생략될 수는 있겠다 싶었지만 좀 그래도 좀 클 것이라고 생각했습니다. 혹시 선생님이 이 문제 어떻게 접근하셨는지 궁금합니다

mch473700 · Answer

아~ 이해했습니다 사실 이전부터 강조하셨던 것이었네요 ㅠㅠ 답변 감사합니다~!

kundol · Answer

안녕하세요 ㅎㅎ mch님이 질문하시는 것을 보면 실력이 늘어간다는 것을 간접적으로 느끼고 있습니다. 좋은 질문입니다. ㅎㅎ 얼핏보면 100개의 격자점에서 상태값은 총 5개이기 때문에 5^100이라고 생각할 수 있습니다. 그러나 문제 조건을 보시면. 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종의 갯수의 제한이 있습니다. 자 그러면. 이렇게 생각할 수 있습니다. 100개의 격자점에서 25개의 상태값을 순서와 상관없이 놓는 경우의 수죠. 100C25라고 생각이 듭니다. 근데 이것또한 큰 수입니다. 242,519,269,720,337,121,015,504 이죠. 그러나 꼭 이래야만 할까요? 5x5 짜리 색종이 4개면 100개의 격자점은 모두 채워지게 됩니다. 그리고 이 경우의 수는 한개밖에 없죠. 자 그러면... 100개의 격자점을 대충 4x4로 감싼다고 했을 때 거의 다 채워지기 때문에 4개정도가 들어가기 때문에 100C4이면 -> 격자점이 다 채워지는 구나 -> 100 C4는 3,921,225(400만) 수준이고 -> 물론 그 외의 격자점을 다른 색종이로 채워야 하겠지만.. -> 400만이면 충분하지 않을까? 그리고... 사실 이것보다는 더 작을 수 있겠다. 라고 생각하고 들어간 것입니다. 격자점은 0과 1로 이루어져있으며. (즉, 매번 100이 아니다.) 5x5로 채울 수 있는 경우의 수들또한 있으니까요. 그리고 100개의 격자점에 4x4가 아니라 사실은 4x4가 채워지면 채울 수 있는 영역 자체가 제한되기 때문에 더 적을 것이라고 생각했습니다. 처음에는 저도 5^100이라고 생각을 했습니다. 그러나 문제 조건을 보았을 때 10x10, 색종이의 갯수제한 5개를 보고 좀 더 작을 것이다. 라고 판단하고 어느정도 유추하고 -> 완탐 -> 줄일 수 있는 것은 줄여보자 -> 휴리스틱 -> 백트래킹 -> 이거 안되면 그리디로 해보자. 라고 했을 때 백트래킹 단계에서 푼 것 같습니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.