안녕하세요 재현님 ㅎㅎ

저도 조건이 색종이가 각 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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. 장재현님.

질문에 대한 답변과 관련된 내용을 찾았습니다. 코드 테스트와 시간 복잡도 관련된 여러 답변들이 문제 접근 방식을 이해하는데 도움이 될 것입니다.

관련 질문과 답변

1. 7-N 시간 복잡도 질문이 있습니다.

   • 이 질문에서는 완전탐색이나 백트래킹의 접근 방법에 대해 다루고 있습니다. 왜 특정 문제에 백트래킹이 적합한지 판단하는 조건을 설명합니다.
     

2. 5-T 질문 있습니다

   • 이 질문에서는 백트래킹을 사용하여 시간 복잡도를 줄이는 방법과 방문 처리 로직의 중요성에 대해 다루고 있습니다. 여기서는 로직의 중복을 줄이고, 더 효율적인 순환 구조에 접근하는 법을 조언합니다.
     

3. 3-G 재귀

   • 이 질문에서는 백트래킹 vs BFS의 효율성 비교와 메모리 초과 문제가 발생했을 때 해결 방법을 다루고 있습니다. 또한 예외 처리를 통해 불필요한 탐색을 줄이는 기법에 대해 설명합니다.
     

추가 설명

1. 격자 문제 접근법
큰돌님께서 제공하신 답변에서, 100개의 격자점에서 25개의 상태값을 놓는다고 언급하셨습니다. 이는 줄여서 접근하는 방법입니다. 직접적으로 모든 가능한 경우의 수를 계산하는 대신, 조건에 맞는 부분 집합을 골라내는 것이 더 효율적입니다.

2. 격자 점을 4x4로 감싼다는 의미
5x5 짜리 색종이를 사용하는 경우, 100개의 격자점이 4개의 색종이로 대부분 채워질 수 있습니다. 남은 공간을 더 작은 색종이로 채우게 될 때 경우의 수가 줄어들기 때문에, 100C4 정도로 경우의 수를 줄여서 생각할 수 있음을 의미합니다. 이는 경우의 수를 줄여서 접근하겠다는 의미로, 백트래킹을 사용하면 해당 케이스들을 효율적으로 탐색할 수 있습니다.

3. 백트래킹 적용 기준
백트래킹을 사용할 지 여부는 다음 조건에 따라 결정됩니다:
- 문제 제약 조건 (예: 메모리 제한, 시간 제한)
- 가능한 상태의 크기
- 방문 체크 방법의 효율성 (예: 메모이제이션, 그리디)

처음에는 완전탐색이나 다이나믹 프로그래밍을 사용해보고, 이는 번갈아가면서 최적화를 시도합니다. 경우에 따라서는 여러 접근 방식을 시도해보며, 효율적인 방법을 찾는 것이 좋습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.