[SUPAC Open Upsolve] 22983 - 조각 체스판(feat. 1915 - 가장 큰 정사각형)

https://www.acmicpc.net/problem/22983

22983번: 조각 체스판

이번에 정식으로는 참여 못했고, 그냥 Open Contest로 참여하게 되었다. 우선, 체스판이 정사각형이기만 하면 되는데, 만약 어느 3x3이 체스판이라면 그 하위에 존재할 수 있는 2x2도 전부 체스판이라는 성격을 발견해서 이를 확장시켜서 이렇게 생각했다.

 

n > 2에서 n x n이 체스판이면, 각 모서리에서 만들 수 있는 (n - 1) x (n - 1)도 전부 체스판이다.

 

근데 이렇게 해서 조금이라도 최적화를 한다고 해도, 나는 그냥 노가다 코드를 짰을 뿐이었고, 결국 시간초과를 받았다.

노가다 코드(실패) :

#include<iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int sum = 0;
    bool use_1 = true;
    static char map[3000][3000];
    static bool valid1[3000][3000];
    static bool valid2[3000][3000];

    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> map[i];
    }
    sum += n * m;

    for(int l = 2; l < min(n, m); l++){
        for(int i = 0; i < n - l + 1; i++){
            for(int j = 0; j < m - l + 1; j++){
                if(l == 2){
                    if(map[i][j] == 'W' && map[i][j + 1] == 'B' && map[i + 1][j] == 'B' && map[i + 1][j + 1] == 'W'){
                        ++sum;
                        valid1[i][j] = true;
                    } else if(map[i][j] == 'B' && map[i][j + 1] == 'W' && map[i + 1][j] == 'W' && map[i + 1][j + 1] == 'B'){
                        ++sum;
                        valid1[i][j] = true;
                    } else {
                        valid1[i][j] = false;
                    }
                } else {
                    if(use_1){
                        if(valid2[i][j] && valid2[i][j + 1]  && valid2[i + 1][j]  && valid2[i + 1][j + 1] ){
                            ++sum;
                            valid1[i][j] = true;
                        } else {
                            valid1[i][j] = false;
                        }
                    } else {
                        if(valid1[i][j] && valid1[i][j + 1]  && valid1[i + 1][j]  && valid1[i + 1][j + 1] ){
                            ++sum;
                            valid2[i][j] = true;
                        } else {
                            valid2[i][j] = false;
                        }
                    }
                }
            }
        }
        use_1 = !use_1;
    }

    cout << sum;

    return 0;
}

뭐야 내 정답 돌려줘요

이번 문젠 아무리 내 대가리로 "다이나믹 프로그래밍"을 하라고 해도 모르겠어서, 이번에 Green55님의 올려준 풀이를 조금 참조해서 풀어보기로 했다. (여러분도 이분 블로그 들어가서 좋은 자료 많이 보세요. 진짜 고인물의 깊이를 느끼실 수 있음)

https://m.blog.naver.com/pasdfq/222488102702

PS 일지 #23

 

다행히, 같이 풀어볼만한 문제를 제시해 주셨다!

https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

그리고 같이 참조할 만한 포스트 :

[ 백준 1915 ] 가장 큰 정사각형 (C++)

풀이를 어느 정도 습득하고 나니까 무슨 소리인줄 알 것 같았다. 이런 피라미드식으로 bool을 저장하는 것 보다는 그 높이를 int로 저장하는 것이 훨씬 이득일 것이라는 생각을 못했는데... 이렇게하면 달랑 O(N * M) 만에 dp연산을 끝낼 수 있다! 처음 2 x 2짜리 맵을 생성하는데 O(N * M), 그리고 dp를 각각 더하는 것 까지 하면, O(3 * N * M)인 것 같은데, 아무튼 2초내에는 끝낼 수 있다.

 

우선, 1915번을 풀어봅시다.

#include<iostream>

using namespace std;

int n, m;
int map[1001][1001];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, maximum = 0;
    cin >> n >> m;

    //한칸 위에다가 저장하는 것이 키포인트!
    for(int i = 1; i <= n; i++){
        string input;
        cin >> input;
        for(int j = 1; j <= m; j++){
            map[i][j] = (int)(input[j - 1] - '0');
        }
    }

    //여기서 -1에 무사히 접근할 수 있다. map은 전역변수로 해두는 것이 좋다.(0 자동 초기화)
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(map[i][j]){
                map[i][j] = min(map[i][j - 1], min(map[i - 1][j], map[i - 1][j - 1])) + 1;
                maximum = max(map[i][j], maximum);
            }
        }
    }

    cout << maximum * maximum;

    return 0;
}

아무튼 몇몇 키포인트를 습득한 나는 이걸 바로 적용해 보기로 했다.

 

코드 :

#include<iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    static char map[3001][3001];
    static int valid[3001][3001];

    int n, m; 
    long sum;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> map[i];
    }
    sum = n * m;

    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < m - 1; j++){
            if(map[i][j] == 'W' && map[i][j + 1] == 'B' && map[i + 1][j] == 'B' && map[i + 1][j + 1] == 'W'){
                valid[i][j] = 1;
            } else if(map[i][j] == 'B' && map[i][j + 1] == 'W' && map[i + 1][j] == 'W' && map[i + 1][j + 1] == 'B'){
                valid[i][j] = 1;
            } else {
                valid[i][j] = 0;
            }
        }
    }

    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < m - 1; j++){
            if(valid[i][j] && i != 0 && j != 0){
                valid[i][j] = min(valid[i - 1][j], min(valid[i][j - 1], valid[i - 1][j - 1])) + 1;
            }
            sum += (long)valid[i][j];
        }
    }

    cout << sum;

    return 0;
}

1915번과는 조금 달랐던 점은 i = 0이나 j = 0일때 valid[i][j] = 1일 수도 있기 땜시, 더해주는 코드를 if문 밖에다 빼야했었다. 아무튼 많이 늦었지만 AC! if문의 내용이 복잡하지 않기 때문이겠지만, 내 코드가 2등으로 빠르다!