24.09.14 19:12 작성
·
25
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
이번 문제를 제가 처음 접했을 때 완탐으로 먼저 생각했습니다. 제가 생각했을 때 격자 마다 5가지 경우의 수가 있다고 생각해서 대략 5^100이라고 생각했습니다. 아무리 색종이가 각 5개라는 조건이 있다해도 5^100 자체가 너무 커서 줄어들어도 시간초과가 날거라고 생각해서 다음 알고리즘으로 dp, 그리디 여러 방법을 도전했는데 실패했습니다.. 그런데 완탐, 백트래킹으로 가능했었다라니 어느 부분에서 그렇게 판단하신건지 궁금하여 커뮤니티를 보았는데 다른 여러 분이 이미 질문을 많이 하셨고 큰돌님께서 답변을 달아주셨습니다. 그런데 그 답변에서 이해가 안되는게 있습니다.
--큰돌님 답변
얼핏보면 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개를 보고 좀 더 작을 것이다. 라고 판단하고 어느정도 유추하고 -> 완탐 -> 줄일 수 있는 것은 줄여보자 -> 휴리스틱 -> 백트래킹 -> 이거 안되면 그리디로 해보자.
라고 했을 때 백트래킹 단계에서 푼 것 같습니다.
이렇게 답변을 하셨는데요 여기서 의문점은 2가지 입니다.
100개의 격자점에서 25개의 상태값을 순서와 상관없이 놓는 경우의 수죠. 이 말씀이 이해가 되지 않습니다. 저도 조건이 색종이가 각 5개라 25개이고 100개의 격자점에서 25개를 골라서 100C25 그 후에 11111,22222,33333,44444,55555 를 나열해서 가능한지 아닌지 판단해야하기 때문에 100C5* 25!/(5!*5!*5!*5!*5!) 이런 경우의 수가 나온다고 생각했습니다. 25!/(5!*5!*5!*5!*5!) 이거는 저렇게 중복된 숫자가 있을 때 나열하는 경우의 수 입니다. 왜 100개의 격자점에서 25개의 상태값을 순서와 상관없이 놓는 경우의 수인지 이해가 잘 되지 않습니다 -> 경우의 수가 이해가 안되는 거지 결론적으로는 너무 크다라는 결론은 이해했습니다.
100개의 격자점을 대충 4x4로 감싼다고 했을 때 거의 다 채워지기 때문에 4개정도가 들어가기 때문에 이 문장이 이해가 가지 않습니다. 4*4로 총 5개까지 들어갈 수 있는거 아닌가요..? 100C5가 아니라 100C4 인지 이해가 되지 않습니다. 100C5라고 생각해서 약 7천만 정도가 나오고 남은 격자도 다른 색종이로 채운다고 생각해서 아마 처음 문제 푼 상태에서 여기까지 생각하더라도 7천만*a(다른 색종이로 채우는 경우의 수) 너무 많구나.. 생각하고 다시 풀어도 백트래킹까진 생각할 자신이 없네요 ㅠㅠ
마지막으로 큰돌님은 어느 정도 경우의수가 나올때 백트래킹으로 시간을 줄여서 성공할 수 있겠구나 라고 생각하시나요..? 일단 도전하고 안되면 빠르게 다음 알고리즘으로 생각을 전환하시는건지 아니면 본인만의 기준이 있으신건지도 궁금합니다!!
답변 2
0
2024. 09. 15. 10:08
안녕하세요 재현님 ㅎㅎ
저도 조건이 색종이가 각 5개라 25개이고 100개의 격자점에서 25개를 골라서 100C25 그 후에 11111,22222,33333,44444,55555 를 나열해서 가능한지 아닌지 판단해야하기 때문에
-> 이부분은 쉽게 판단하기 위해 색종이의 크기를 배제하여 100C25라 표현한 것입니다. 색종이 크기까지 고려해서 경우의 수 잡기는 어렵습니다. -> 처음에 문제를 접했을 때 이런식으로 어느정도 어림잡아 생각하는 것이 좋습니다.
하지만 한번 정확히 계산해볼까요?
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int grid[N][N];
int paper_count[6] = {0, 5, 5, 5, 5, 5};
bool canPlace(int y, int x, int size) {
if (y + size > N || x + size > N) return false;
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
if (grid[y + i][x + j] != 1) return false;
}
}
return true;
}
void place(int y, int x, int size, int value) {
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
grid[y + i][x + j] = value;
}
}
}
int solve(int y, int x) {
if (y == N) return 1;
if (x == N) return solve(y + 1, 0);
if (grid[y][x] == 0) return solve(y, x + 1);
int total = 0;
for (int size = 1; size <= 5; ++size) {
if (paper_count[size] > 0 && canPlace(y, x, size)) {
place(y, x, size, 0);
paper_count[size]--;
total += solve(y, x + 1);
place(y, x, size, 1);
paper_count[size]++;
}
}
return total;
}
int main() {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> grid[i][j];
}
}
int result = solve(0, 0);
cout << result << "\n";
return 0;
}
입력:
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
출력:
3925
총 경우의 수는 3925 수준으로 굉장히 적게 나오는 것을 알 수 있습니다.
100개의 격자점을 대충 4x4로 감싼다고 했을 때 거의 다 채워지기 때문에 4개정도가 들어가기 때문에 이 문장이 이해가 가지 않습니다. 4*4로 총 5개까지
-> 10 * 10의 격자점이 있을 때 4 짜리 색종이로 4개밖에 못들어갑니다. 어떻게 5개가 들어가나요?
생각하고 다시 풀어도 백트래킹까진 생각할 자신이 없네요 ㅠㅠ
-> 음 문제를 처음에 봤을 때 문제 범위를 보고 너무 시간복잡도가 크구나 라는 생각을 가질수는 있습니다. 그러나 이문제는 내가 실제로 색종이를 붙여본다고 생각했을 때 -> 경우의 수가 그렇게 많이는 나오지 않는구나 하고 생각할 수 있습니다. 예를 들어 4짜리 붙인다고 했을 때 사실 말이 100C4이지 붙일 수 있는 경우의 수 자체가 그렇게 많지는 않을 겁니다.
자 그러면.. 그냥 효율적으로 붙여볼까 하고 판단할 수도 있지만 -> 일단 무식하게 먼저 큰돌님이 해보라고 했으니 -> 무식하게 해보자 -> 생각해보니 이거 색종이가 큰 것 부터 하면 경우의 수 줄일 수 있겠네 -> 백트래킹 -> 이게 안되면 효율적으로 하는 그리디한 방법을 생각해보자.
이렇게 들어가시면 됩니다.
어느 정도 경우의수가 나올때 백트래킹으로 시간을 줄여서 성공할 수 있겠구나 라고 생각하시나요..?
-> 보통은 1억까지는 괜찮다고 생각하고 + 앞의 답변처럼 들어가시면 됩니다.
즐거운 추석보내세요 ㅎㅎ
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. 장재현님.
질문에 대한 답변과 관련된 내용을 찾았습니다. 코드 테스트와 시간 복잡도 관련된 여러 답변들이 문제 접근 방식을 이해하는데 도움이 될 것입니다.
1. 격자 문제 접근법
큰돌님께서 제공하신 답변에서, 100개의 격자점에서 25개의 상태값을 놓는다고 언급하셨습니다. 이는 줄여서 접근하는 방법입니다. 직접적으로 모든 가능한 경우의 수를 계산하는 대신, 조건에 맞는 부분 집합을 골라내는 것이 더 효율적입니다.
2. 격자 점을 4x4로 감싼다는 의미
5x5 짜리 색종이를 사용하는 경우, 100개의 격자점이 4개의 색종이로 대부분 채워질 수 있습니다. 남은 공간을 더 작은 색종이로 채우게 될 때 경우의 수가 줄어들기 때문에, 100C4 정도로 경우의 수를 줄여서 생각할 수 있음을 의미합니다. 이는 경우의 수를 줄여서 접근하겠다는 의미로, 백트래킹을 사용하면 해당 케이스들을 효율적으로 탐색할 수 있습니다.
3. 백트래킹 적용 기준
백트래킹을 사용할 지 여부는 다음 조건에 따라 결정됩니다:
- 문제 제약 조건 (예: 메모리 제한, 시간 제한)
- 가능한 상태의 크기
- 방문 체크 방법의 효율성 (예: 메모이제이션, 그리디)
처음에는 완전탐색이나 다이나믹 프로그래밍을 사용해보고, 이는 번갈아가면서 최적화를 시도합니다. 경우에 따라서는 여러 접근 방식을 시도해보며, 효율적인 방법을 찾는 것이 좋습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
2024. 09. 16. 14:45
10 * 10의 격자점이 있을 때 4 짜리 색종이로 4개밖에 못들어갑니다. 어떻게 5개가 들어가나요?
제가 잘못생각했네요...ㅎㅎ 자세히 답변해주셔서 감사합니다. 완벽히 이해됐습니다!