7-N 시간 복잡도 접근 질문드립니다.
234
16 asked
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
단순히 한 자리에서 5번 호출, 영향을 받을 수 있는 지점 99개가 있으므로 최대 약 5^99 이라고 생각했거든요.
5x5의 색종이를 붙이니까 영향 받는 타일이 더 생략될 수는 있겠다 싶었지만 좀 그래도 좀 클 것이라고 생각했습니다.
혹시 선생님이 이 문제 어떻게 접근하셨는지 궁금합니다
Answer 2
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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
코딩 살구 클럽 로그인 문제
0
25
1
2-J 채점관련 질문
0
25
3
코딩 살구 클럽 Python 지원 가능 여부
0
45
1
살구클럽 아이디 없음 문제
0
55
1
1-O 코딩살구클럽 채점관련 질문
0
45
2
히든 테스트 케이스가 사라졌습니다
0
42
1
채점서버 혹시 다른 언어 지원도 가능하게 해주실 수 있나요
1
54
2
살구 클럽 채점 관련 문의(테스트 케이스)
0
52
2
1-H 문제 채점하기 오류
0
47
3
코딩살구클럽 2주차 2-L 문제 채점하기 오류
0
42
2
살구 클럽 채점 관련 문의
0
55
2
코딩 살구 클럽 실전 세션
0
48
2
코딩살구클럽 채점 관련 질문
0
42
2
코딩살구클럽 컴파일에러
0
74
2
5-B
0
47
2
4 - A
0
51
2
코딩살구클럽 입장이 안됩니다
0
124
2
4-F 경우의 수 질문입니다.
0
53
2
코딩살구클럽 가입이 안됩니다.
0
119
2
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
76
1
교안 158페이지 문의드립니다
0
53
2
코딩살구클럽 관련 건의사항
0
161
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
54
1
진행 방법 질문드립니다!
0
102
2