글 읽기 - 반례를 알고 싶습니다ㅠ

wnsgur1714 4년 전 0

ches - 체스판

namun - 해당 색깔의 가능한 칸의 수

dgs - 대각선을 저장

아무리 찾아봐도 반례가 무엇인지 모르겠습니다ㅠ

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int> > ches;
vector<vector<int> > namun;
int value1;
int value2;
vector<vector<int> > dgs;

void fid1(int x, int y, int gs){
    if(gs + namun[y][x] <= value1){
        return;
    }
    if(y == n){
        value1 = max(gs, value1);
    }
    else{
        if(ches[y][x] && !dgs[0][x+y] && !dgs[1][x-y+n-1]){
            dgs[0][x+y] = dgs[1][x-y+n-1] = 1;
            if(x+2 >= n){
                fid1((x+2)%n, y+1, gs+1);
            }
            else{
                fid1(x+2, y, gs+1);
            }
            dgs[0][x+y] = dgs[1][x-y+n-1] = 0;
        }
        if(x+2 >= n){
            fid1((x+2)%n, y+1, gs);
        }
        else{
            fid1(x+2, y, gs);
        }
    }
}

void fid2(int x, int y, int gs){
    if(gs + namun[y][x] <= value2){
        return;
    }
    if(y == n){
        value2 = max(gs, value2);
    }
    else{
        if(ches[y][x] && !dgs[0][x+y] && !dgs[1][x-y+n-1]){
            dgs[0][x+y] = dgs[1][x-y+n-1] = 1;
            if(x+2 >= n){
                fid2((x+2)%n, y+1, gs+1);
            }
            else{
                fid2(x+2, y, gs+1);
            }
            dgs[0][x+y] = dgs[1][x-y+n-1] = 0;
        }
        if(x+2 >= n){
            fid2((x+2)%n, y+1, gs);
        }
        else{
            fid2(x+2, y, gs);
        }
    }
}


int main(){
    cin >> n;
    ches.resize(n+1);
    dgs.resize(2);
    dgs[0].resize(2*n-1);
    dgs[1].resize(2*n-1);
    for(int i = 0 ; i < n ; i++){
        ches[i].resize(n+1);
        for(int j = 0 ; j < n ; j++){
            cin >> ches[i][j];
        }
    }
    namun.resize(n+1);
    namun[n].resize(2);
    for(int i = n-1 ; i >= 0 ; i--){
        namun[i].resize(n+1);
        namun[i][n-1] = namun[i+1][1];
        namun[i][n-2] = namun[i+1][0];
        if(ches[i][n-1]){
            namun[i][n-1]++;
        }
        if(ches[i][n-2]){
            namun[i][n-2]++;
        }
        for(int j = n-3 ; j >= 0 ; j--){
            namun[i][j] = namun[i][j+2];
            if(ches[i][j]){
                namun[i][j]++;
            }
        }
    }
    fid1(0, 0, 0);
    fid2(1, 0, 0);
    cout << value1 + value2;
    return 0;
}

wnsgur1714 4년 전 0

찾았습니다. n이 홀수일 때와 짝수일 때를 똑같이 생각했네요.

wnsgur1714 4년 전 0

틀렸습니다가 뜨네요... 이건 또 뭐가 문제일까요...

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int> > ches;
vector<vector<int> > namun;
int value1;
int value2;
vector<vector<int> > dgs;

void fid1(int x, int y, int gs){
    if(gs + namun[y][x] <= value1){
        return;
    }
    if(y == n){
        value1 = max(gs, value1);
    }
    else{
        if(ches[y][x] && !dgs[0][x+y] && !dgs[1][x-y+n-1]){
            dgs[0][x+y] = dgs[1][x-y+n-1] = 1;
            if(x+2 >= n){
                if(n%2 == 1){
                    fid1((x+2)%n, y+1, gs+1);
                }
                else{
                    fid1((((x+2)%n)+1)%2, y+1, gs+1);
                }
            }
            else{
                fid1(x+2, y, gs+1);
            }
            dgs[0][x+y] = dgs[1][x-y+n-1] = 0;
        }
        if(x+2 >= n){
            if(n%2 == 1){
                fid1((x+2)%n, y+1, gs);
            }
            else{
                fid1((((x+2)%n)+1)%2, y+1, gs);
            }
        }
        else{
            fid1(x+2, y, gs);
        }
    }
}

void fid2(int x, int y, int gs){
    if(gs + namun[y][x] <= value2){
        return;
    }
    if(y == n){
        value2 = max(gs, value2);
    }
    else{
        if(ches[y][x] && !dgs[0][x+y] && !dgs[1][x-y+n-1]){
            dgs[0][x+y] = dgs[1][x-y+n-1] = 1;
            if(x+2 >= n){
                if(n%2 == 1){
                    fid2((x+2)%n, y+1, gs+1);
                }
                else{
                    fid2((((x+2)%n)+1)%2, y+1, gs+1);
                }
            }
            else{
                fid2(x+2, y, gs+1);
            }
            dgs[0][x+y] = dgs[1][x-y+n-1] = 0;
        }
        if(x+2 >= n){
            if(n%2 == 1){
                fid2((x+2)%n, y+1, gs);
            }
            else{
                fid2((((x+2)%n)+1)%2, y+1, gs);
            }
        }
        else{
            fid2(x+2, y, gs);
        }
    }
}


int main(){
    cin >> n;
    ches.resize(n+1);
    dgs.resize(2);
    dgs[0].resize(2*n-1);
    dgs[1].resize(2*n-1);
    for(int i = 0 ; i < n ; i++){
        ches[i].resize(n+1);
        for(int j = 0 ; j < n ; j++){
            cin >> ches[i][j];
        }
    }
    namun.resize(n+1);
    namun[n].resize(2);
    for(int i = n-1 ; i >= 0 ; i--){
        namun[i].resize(n+1);
        namun[i][n-1] = namun[i+1][1];
        namun[i][n-2] = namun[i+1][0];
        if(ches[i][n-1]){
            namun[i][n-1]++;
        }
        if(ches[i][n-2]){
            namun[i][n-2]++;
        }
        for(int j = n-3 ; j >= 0 ; j--){
            namun[i][j] = namun[i][j+2];
            if(ches[i][j]){
                namun[i][j]++;
            }
        }
    }
    fid1(0, 0, 0);
    fid2(1, 0, 0);
    cout << value1 + value2;
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 알고 싶습니다ㅠ

wnsgur1714 4년 전 0

wnsgur1714 4년 전 0

wnsgur1714 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말