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

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

안녕하세요 ㅎㅎ

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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.