인프런 커뮤니티 질문&답변
작성한 질문수
7-N 시간 복잡도 접근 질문드립니다.
작성
·
149
0
답변 2
0
0
안녕하세요 ㅎㅎ
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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.