글 읽기 - c++ 시간초과가 나는 이유를 모르겠습니다

jonghyuk1203 1년 전 0

아무리 봐도 O(NM)인데 어디서 느려지는 걸까요...

#include <bits/stdc++.h>

#define endl '\n'
typedef long long ll;
#define setting cin.tie(0)->sync_with_stdio(0)
using namespace std;

int main(){
  setting;

  string A, B;
  cin >> A >> B;

  int A_size = A.size();
  int B_size = B.size();

  int Dp[A_size + 1][B_size + 1];
  string Lcs[A_size + 1][B_size + 1];

  for (int i = 0; i <= A_size; ++i) {
    for (int j = 0; j <= B_size; ++j) {
      if (i == 0 || j == 0){
        Dp[i][j] = 0;
        Lcs[i][j] = "";
        continue ;
      }
      if (A[i - 1] == B[j - 1]){
        Dp[i][j] = Dp[i - 1][j - 1] + 1;
        Lcs[i][j] = Lcs[i - 1][j - 1] + A[i - 1];
      }
      else{
        if (Dp[i - 1][j] > Dp[i][j - 1]){
          Dp[i][j] = Dp[i - 1][j];
          Lcs[i][j] = Lcs[i - 1][j];
        }
        else{
          Dp[i][j] = Dp[i][j - 1];
          Lcs[i][j] = Lcs[i][j - 1];
        }
      }
    }
  }

  cout << Dp[A_size][B_size] << endl << Lcs[A_size][B_size];
}

jonghyuk1203 1년 전 0

그냥 string이 겁나 느린 거였네요 역추적하시면 됩니다

kidw0124 1년 전 3

string이 느린거라기 보다 string이차원 배열을 만들면 문자열을 대입하는 과정에서 string문자열 길이만큼 시간을 잡아먹기 때문에 문자열 길이를 N이라고 하면(질문자님께서 N, M나눴지만 하나로 보겠습니다) O(N^2)이 아니라 O(N^3)코드입니다. char로 잘 푸신것 같은데, 혹시나 "string이 느리다"라는 오해를 하실까봐 남겨드립니다!

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

문제

문제

출처

ICPC

c++ 시간초과가 나는 이유를 모르겠습니다

jonghyuk1203 1년 전 0

jonghyuk1203 1년 전 0

kidw0124 1년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말