WILDCARD 예외 케이스 문의드립니다.

  • kingman562
    kingman562

    WILDCARD

    오답으로 나오는데 예외 케이스를 찾기 힘들어서 문의드립니다.
    재귀호출 + 메모이제이션으로 작성했습니다.
    감사합니다.

    #include <stdio.h>
    #include <string.h>
    char W[102], sol[501][102], ls[102], temp[102];
    int dp[102][102], N, C;
    
    int dfs(int wn, int lsn){
        if (dp[wn][lsn] != -1)return dp[wn][lsn];
        if (W[wn] == 0 && ls[lsn] == 0)return 1;
        if (W[wn] == '*'&&ls[lsn] == 0){
            if (dfs(wn + 1, lsn) == 1)return 1;
        }
        if (ls[lsn] == 0) return 0;
        if (W[wn] == '?'){
            if (dfs(wn + 1, lsn + 1) == 1)return 1;
        }
        else if (W[wn] == '*'){
            if (dfs(wn, lsn + 1) == 1)return 1;
            if (dfs(wn + 1, lsn) == 1)return 1;
        //  if (dfs(wn + 1, lsn + 1) == 1)return 1;
        }
        else if (W[wn] == ls[lsn]){
            if (dfs(wn + 1, lsn + 1) == 1)return 1;
        }
        return dp[wn][lsn] = 0;
    }
    
    int main(void)
    {
        int i, j, cnt = 0, k, flag = 0;
    
        scanf("%d", &C);
        for (int tc = 1; tc <= C; tc++){
            for (i = 0; i <= 101; i++){
                W[i] = 0;
            }
            scanf("%s", &W);
            scanf("%d", &N);
            for (int tcc = 1; tcc <= N; tcc++){
                for (i = 0; i <= 101; i++){
                    ls[i] = 0;
                    for (j = 0; j <= 101; j++){
                        dp[i][j] = -1;
                    }
                }
    
                scanf("%s", &ls);
                if (dfs(0, 0)){
                    for (i = 0; i <= 101; i++){
                        sol[cnt][i] = ls[i];
                    }
                    cnt++;
                }
            }
    
        }
        for (i = 0; i <= 500; i++){
            if (sol[i][0] == 0)break;
            for (j = i + 1; j <= 500; j++){
                if (sol[j][0] == 0)break;
                if (strcmp(sol[i], sol[j]) > 0){
                    strcpy(temp, sol[i]);
                    strcpy(sol[i], sol[j]);
                    strcpy(sol[j], temp);
                }
            }
        }
        i = 1;
    
        for (i = 0; i <= 500; i++){
            if (sol[i][0] == 0)break;
            printf("%s\n", sol[i]);
        }
        return 0;
    }
    

    7년 전
2개의 댓글이 있습니다.
  • Corea
    Corea

    각 테스트 케이스마다 출력을 해야 합니다. 모든 테스트 케이스에 대해 한 번에 출력을 하셨네요.


    7년 전 link
  • kingman562
    kingman562

    감사합니다 논리에 오류가 있는줄 알고 출력에 신경을 안썻네요 ㅠㅠ


    7년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.