2-E 분할정복 반례를 찾지 못하겠습니다.

안녕하세요 ㅎㅎ

잘 짜셨네요. ㅎㅎ

제 생각에는 굳이 n == 1일 때 나눈부분이 잘 못된 것 같습니다. 저렇게 안나누어도 바로 되는 훌륭한 코드입니다.

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

string a[64][64];
int n, ny, nx;
string ret, temp;
int dy[] = {0, 0, 1, 1};
int dx[] = {0, 1, 0, 1};

string four(int num, int y, int x){  
    if(num == 1){
        return a[y][x];
    }
    else{
        string s = "";
        for(int i = 0; i < 4; i++){
            ny = y + dy[i] * (num / 2);
            nx = x + dx[i] * (num / 2);
            s += four(num / 2, ny, nx);
        }
        if(s == "0000") return "0";
        else if(s == "1111") return "1";
        else return "(" + s + ")";
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> temp;
        for(int j = 0; j < n; j++){
            a[i][j] = temp[j];
        }
    }
    
    ret = four(n, 0, 0);
    cout << ret << '\n';
    
    return 0;
}

이렇게 해보시겠어요?

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다.

JeongJuLee님 코드에서 분할정복 부분의 로직은 올바르게 구현된 것으로 보입니다.하지만, "0000"이나 "1111"일 때만 압축을 진행하는 그 조건이 문제가 될 수 있습니다. 유의하셔야 할 것은 모든 0들 또는 모든 1들로만 이루어진 더 큰 부분 배열에 대해서도 압축이 이루어져야 한다는 점입니다. 기존 코드는 2x2 부분 배열에 대해 압축하는 로직으로 보이는데, 이는 n이 더 클 때 정상적으로 압축되지 않을 수 있습니다.

제시된 코드에서 주어진 배열의 모든 값을 확인하여 압축이 가능한지를 재귀적으로 확인하고 있고, 각 구역의 결과값을 재귀 호출로 합쳐 조건에 맞게 압축하거나 괄호를 추가하는 구현을 하셨습니다. 반환되는 문자열을 검사할 때는 4개의 ‘0’ 혹은 ‘1’이 연속된 문자열인지를 체크하지만, 더 큰 크기의 전체 구역이 같은 값으로 이루어져 있을 때 이를 문자 하나인 ‘0’ 또는 ‘1’로 압축해야 할 수 있습니다. 이를 감안하여 추가적인 로직 검토가 필요합니다.

또한 기저 사례에서 n == 1 인 경우, 압축 결과를 괄호로 묶어 출력하는 것은 문제의 요구사항에 따라 다를 수 있기 때문에, 문제의 상세한 조건을 다시 한번 확인하시기 바랍니다.

반례를 찾는 데 어려움이 계속된다면, 더 다양한 입력 값에 대해서 결과를 출력해보고 예상과 다른 부분이 있다면 그 부분을 중점적으로 검토해보시는 것이 좋습니다. 예를 들어 n이 2보다 클 때 더 큰 배열에 대해서도 올바르게 압축하는지 테스트해볼 필요가 있습니다.

잠재적인 문제가 수정되고 나면, 다시 예제 입력 및 추가적인 다양한 입력을 통해 코드를 테스트해 보세요. 만약 이후에도 문제가 해결되지 않는다면, 해당 강의의 커뮤니티 질문&답변 게시판에 직접 질문을 올리시면 강사님이 확인 후 답변을 드릴 수 있습니다.

도움이 필요하시면 언제든지 문의하세요. 추가적인 질문이 있으시면 도와드릴 준비가 되어 있습니다. 화이팅입니다!