글 읽기 - 이 코드의 반례는 무엇일까요?

cgc96 4년 전 0

위,왼위,왼이 0이아닌 같은 수이면 d[i],[j]를 d[i][j-1] + 1로 업데이트해주고

d[i],[j]는 위,왼위,왼이 0이아닐때 셋중 가장 큰수로 업데이트합니다.

반례가 궁금하네요

#include <iostream>
#include <cstdio>

using namespace std;

int d[1001][1001];

int main(){
    int n, m, x; scanf("%d %d", &n, &m);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            scanf("%1d", &x);
            if(x == 0) d[i][j] = 0;
            else {
                d[i][j] = 1;
            
                if(d[i-1][j] != 0 && d[i-1][j] == d[i][j-1] && d[i-1][j] == d[i-1][j-1]){
                    d[i][j] = d[i-1][j] + 1;
                }
                else{
                    if(d[i-1][j] != 0 && d[i][j-1] != 0 && d[i-1][j-1] != 0)
                        d[i][j] = max(max(d[i][j-1], d[i-1][j-1]), d[i-1][j]);
                }
            }
            if(d[i][j] > ans)
                ans = d[i][j];
        }
    }
    printf("%d\n", ans*ans);
}

dyk777 4년 전 4

왜 가장 큰 수로 업데이트되어야 한다고 생각하셨나요?

반례는 다음과 같은 반례가 있습니다.

5 5
11100
11110
11111
01111
00111

Test    output: 25
Correct answer:  9

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

문제

문제

출처

ICPC

이 코드의 반례는 무엇일까요?

cgc96 4년 전 0

dyk777 4년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말