inflearn logo
강의

Course

Instructor

Coding Test Practice Test (with C++): For Large Companies

4. String and Score Problem Solution (LCS Dynamic Application: DP)

이렇게 풀면 반례가 어떻게되나요?

245

jw2914901790

2 asked

0


#include <bits/stdc++.h>

using namespace std;

int LCSubstr(string x, string y){
    int n = x.size(), m=y.size();

    vector<vector<int>> dy(n+1,vector<int>(m+1,0));

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(x[i-1] == y[j-1])
                dy[i][j] = dy[i-1][j-1] + 1;
            else
                dy[i][j] = max(dy[i-1][j], dy[i][j-1]);
        }
    }
    
    return dy[n][m];
}

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    int n1,n2,n3;
    string A,B;
    
    cin >> n1 >> n2 >> n3;
    cin >> A >> B;
    
    int LCSLength = LCSubstr(A, B);
    int SpaceLength = abs(int(A.size() - B.size()));
    int strLength = max(A.size(),B.size());
    
    int N1Score = LCSLength * n1; //최대공통부분 문자열 길이 * 점수
    int N2Score = SpaceLength * n2;//공백갯수 * 점수
    int N3Score = (strLength - LCSLength - SpaceLength) * n3;//(전체길이 - 공백갯수 - 최대공통부분 문자열 길이) * 점수
    
    cout << N1Score + N2Score + N3Score;
    return 0;
}

코테 준비 같이 해요! C++

Answer 1

0

jw2914901790

아.. 강의보고 알았습니다.

abc

acb

라고 해서 무조건 공백이 없다고 생각하면 안되군요..

a "" b  c

a  c  b  "" 이게 더 최대값이 나오니까요

에고

조합을 구할때 algorithm 함수 next_permutation 사용 가능 여부

0

457

1

최악의 경우 연산 질문이 있습니다.

0

411

1

로컬 환경과 다르게 오답이라고 나와서 문의 드립니다.

0

302

1

6강 3번 정사각형 그리키 코드 질문 드립니다.

0

242

1

1-5 효율적인 공부 dy를 시간(N)으로 하는 풀이 질문

0

320

1

반복수와 시간초 계산을 어떻게 하나요??

0

333

1

왜 DP로 풀어야하는지 궁금합니다

0

242

1

선생님 안녕하세요. 다른 풀이에 대한 질문이 있습니다.

0

223

1

문제 해결방법에 대한 질문이 있습니다.

0

245

0

바둑대회 코딩 질문

0

270

1

6분 11초에서 dis [0][][]3차원 격자판이있는데요. 격자판안에 숫자는 문제에 없던데 어떻게 구해지는건가요?

0

200

0

실전모의고사 5회 1번 패턴찾기 질문있습니다.

0

220

1

전역변수관련 질문입니다.

0

255

1

5-1 패턴찾기 문제 질문드립니다.

0

218

1

오렌지 나무 문제 질문드립니다

0

310

1

코드 한번 봐주시면 감사하겠습니다!

0

175

1

코드 한번 봐주시면 감사하겠습니다!

0

234

1

코드 한번 봐주시면 감사하겠습니다!

0

198

1

시작점의 ch

0

204

1

vector에서 질문이 있습니다~!

0

235

1

그대로 따라했는데 시간 초과가 나왔습니다

0

161

1

2회 모의고사 4번 숲속의 기사 코드 질문이 있습니다.

0

288

1

질문있습니다.

0

209

1

1회 1번 공통 문자열 문제 설명 보충하시면 더 좋을 것 같습니다!

0

221

1