글 읽기 - 14%에서 틀리는분들

hhhjs0133 1년 전 0

문제에서 최소 한개의 블록을 준다했으므로 max_value의 최소값은 2입니다

그래서 max_value 최솟값을 0이 아니라 2로 수정하고 했더니 잘됩니다

근데 제생각엔 0으로 놓고 해도 전수조사 하기 떄문에 2가 나와야하는데 문제오류인것 같습니다

djm03178 1년 전 1

확인해 본 결과 답이 2보다 작은 케이스는 없습니다.

http://boj.kr/8af1d125550d4793...

그렇게 판단하신 코드를 올려주세요.

hhhjs0133 1년 전 0

일단 제코드에서 매번 백트래킹으로 진입하기 전에 board에 있는 최대값을 전부 조사하는데요

여기서 max_val 이 0이면 14%에서 틀리고 2로 수정하면 통과해서 그렇게 추측했습니다.

아래는 제코드 입니다

#include <bits/stdc++.h>
using namespace std;

int board[25][25];
int max_val = 2;
int n;

void move(int dir){
    if(dir == 1){
        for(int i=0; i<n; i++){
            int position=0;
            int ptr=0;
            int flag=1;
            if(board[i][position]){
                position++;
                ptr++;
            }
            for(; ptr<n; ptr++){

                if(board[i][ptr] == 0) continue;
                else{
                        if(board[i][position-1] == board[i][ptr] && flag){
                            board[i][position-1] = board[i][position-1] * 2;
                            board[i][ptr] = 0;
                            flag=0;
                        }
                        else{
                            if(position != ptr){
                                board[i][position++] = board[i][ptr];
                                board[i][ptr] = 0;
                            }
                            else position++;
                            flag=1;
                        }
                    }
                
            }
        }
    }

    else if(dir == 2){
        for(int i=0; i<n; i++){
            int position=0;
            int ptr=0;
            int flag=1;
            if(board[position][i]){
                position++;
                ptr++;
            }
            for(; ptr<n; ptr++){

                if(board[ptr][i] == 0) continue;
                else{

                        if(board[position-1][i] == board[ptr][i] && flag){
                            board[position-1][i] = board[position-1][i] * 2;
                            board[ptr][i] = 0;
                            flag=0;
                        }
                        else{
                                if(position != ptr){
                                    board[position++][i] = board[ptr][i];
                                    board[ptr][i] = 0;
                                }
                                else position++;
                                flag=1;
                        }
                    
                }
            }
        }
    }

    else if(dir == 3){
        for(int i=0; i<n; i++){
            int position=n-1;
            int ptr=n-1;
            int flag=1;

            if(board[i][position]){
                position--;
                ptr--;
            }

            for(; ptr>=0; ptr--){

                if(board[i][ptr] == 0) continue;
                else{

                        if(board[i][position+1] == board[i][ptr] && flag){
                            board[i][position+1] = board[i][position+1] * 2;
                            board[i][ptr] = 0;
                            flag=0;
                        }
                        else{
                            if(position != ptr){
                                board[i][position--] = board[i][ptr];
                                board[i][ptr] = 0;
                            }
                            else position--;
                            flag=1;
                        }
                    
                }
            }
        }
    }

    else if(dir == 4){
        for(int i=0; i<n; i++){
            int position=n-1;
            int ptr=n-1;
            int flag=1;
            if(board[position][i]){
                position--;
                ptr--;
            }
            for(; ptr>=0; ptr--){
                if(board[ptr][i] == 0) continue;
                else{
                        if(board[position+1][i] == board[ptr][i] && flag){
                            board[position+1][i] = board[position+1][i] * 2;
                            board[ptr][i] = 0;
                            flag=0;
                        }
                        else{
                            if(position != ptr){
                                board[position--][i] = board[ptr][i];
                                board[ptr][i] = 0;
                            }
                            else position--;
                            flag=1;
                        }
                }
            }
        }
    }


}

void func(int k){
    for(int i=0; i<n; i++){
            int a;
            a = *max_element(board[i], board[i]+n);
            max_val = max(max_val,a);
    }

    if(k==6){
        return;
    }

    for(int i=1; i<=4; i++){
        int temp[25][25];
        
        for(int p=0; p<n; p++){
            for(int q=0; q<n; q++){
                temp[p][q] = board[p][q];
            }
        }

        move(i);
        func(k+1);
        
        for(int p=0; p<n; p++){
            for(int q=0; q<n; q++){
                board[p][q] = temp[p][q];
            }
        }
    }
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    
    for(int i=0; i<n; i++) fill(board[i], board[i]+n, 0);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> board[i][j];

    func(1);

    cout << max_val;

}

djm03178 1년 전 2

코드에 undefined behavior가 있다고 추정됩니다. 출력 직전에 assert(max_val >= 2);를 해도 런타임 에러가 아닌 틀렸습니다가 나오며, max_val의 선언 위치를 board의 위쪽으로 옮기기만 해도 int max_val = 0;으로 써도 통과됩니다.

정확히 본 것인지는 모르겠으나, 22번째 줄과 같은 부분에서 첫 칸이 비어있는 경우 position이 0인 상태에서 board[i][position - 1]에 접근하게 될 것 같습니다.

hhhjs0133 1년 전 0

아 말씀하신부분이 맞습니다

감사합니다

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

문제

문제

출처

ICPC

14%에서 틀리는분들

hhhjs0133 1년 전 0

djm03178 1년 전 1

hhhjs0133 1년 전 0

djm03178 1년 전 2

hhhjs0133 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말