글 읽기 - 어디가 잘못된 걸까요?

otome 2년 전 0

상상 가능한 웬만한 반례는 다 통과하는데 정작 제출하면 3%에서 틀려서 막막하네요 ㅠㅠ

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
/*
 https://8iggy.tistory.com/159?category=997927
 https://8iggy.tistory.com/160
 https://velog.io/@timevoyage/leetcode-1143-Longest-Common-Subsequence
 https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence
*/
string P, Q, s;
vector<vector<int>> dp;
int p, q, lenp, lenq;
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> P >> Q;
    dp.resize(P.size()+1,vector<int> (Q.size()+1,0));
    lenp = P.size();
    lenq = Q.size();
    for (p=1;p<=lenp;p++){
        for (q=1;q<=lenq;q++){
            dp[p][q]=(P[p-1]==Q[q-1])?dp[p-1][q-1]+1:max(dp[p-1][q],dp[p][q-1]);
        }
    } 
    /*
    cout << "    ";
    for (int q=0;q<Q.size();q++) cout << Q[q] << " ";
    cout << endl;
    for (int p=0;p<=P.size();p++){
        if (p>0) cout << P[p-1] << " ";
        else cout << "  ";
        for (int q=0;q<=Q.size();q++){
            cout << dp[p][q] << " ";
        }
        cout << endl;
    }*/
    for (p=lenp,q=lenq;;){
        if (dp[p][q]==0) break;
        if (dp[p-1][q]==dp[p][q-1]) {
            if(dp[p][q]>dp[p-1][q-1]) s = Q[q-1] + s;
            p--;
            q--;
            continue;
        }
        else {
            if (dp[p-1][q]>dp[p][q-1]){
                p--;
                continue;
            }
            else {
               q--;
               continue;
            }
        }
    }
    cout << s.size();
    if (s.size()) cout << endl << s;
}

otome 2년 전 0

마지막에 for 문을 아래로 바꾸니까 되네요

while(p&&q){

if (dp[p-1][q]==dp[p][q]){

--p;

}

else if (dp[p][q-1]==dp[p][q]){

--q;

}

else{

--p;

--q;

s = P[p] + s;

}

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

문제

문제

출처

ICPC

어디가 잘못된 걸까요?

otome 2년 전 0

otome 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말