7-S 시간초과 질문드립니다 !!

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

7-S

작성

157

수정됨

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요. 강사님

강의 잘 듣고 잇습니다.

강평 별5개 드렸습니다 항상 감사합니다 ^^

강의도 들어보았고, 제가 작성한 코드와 로직은 같은 것이라고 저는 생각하는데.. 제출시 시간초과가 떠서요..

무엇이 잘못됫는지 여쭙고 싶습니다.

감사합니다.

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

string S;
bool DP[2505][2505]; // 시작과 끝에 대한 팰린드롬 문자열의 길이
int DP2[2505];
#define INF 987654321

bool go(pair<int, int> Q){
    if (Q.first >= Q.second){
        return true;
    }
    
    bool& ret = DP[Q.first][Q.second];
    if(ret) return ret;

    if (S[Q.first] == S[Q.second]){
        ret = go({Q.first+1, Q.second-1});
    }

    return ret;
}

int go2(int here){
    if(here >= S.size()) return 0; 

    int &ret = DP2[here]; 
    if(ret != INF) return ret;

    for(int i = here; i < S.size(); ++i){
        if (DP[here][i]){
            ret = min(ret, go2(i+1)+1);
        }
    }

    return ret; 
}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> S;
  
    for(int i =0 ; i < S.size(); ++i){
        DP[i][i] = 1;
        for(int j = i+1; j < S.size(); ++j){
            go({i,j});
        }
    }

    fill(DP2, DP2+2505, INF);
    cout << go2(0);

    return 0;
}

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 윽쓰님 ㅎㅎ

    for(int i =0 ; i < S.size(); ++i){
        DP[i][i] = 1;
        for(int j = i+1; j < S.size(); ++j){
            go({i,j});

일단은...

이부분에서 시간초과가 발생하는 것 같습니다. - 재귀함수 호출

뭔 의미인지는 알겠습니다만 i, j 가 모든 쌍에서 시작함 - 저게 시작과 끝 부분을 의미하고...

그렇게 되면

1, 4 -> 2, 3 으로 이어지게 되겠죠?

근데 이경우 2, 3이 펠린드롬 -> 1, 4인 경우를 체크하는 효율적인 로직이 이어지지 않습니다. (즉, 비효율적)

그러면서 매번 쌍 자체가 펠린드롬인지를 확인하느라 시간이 많이 걸릴 것 같습니다. - 메모이제이션을 걸어도 -> 불필요한 함수호출은 발동.

제 생각에는 이런 코드를 원하신게 아닐까요?

해당 부분을 고쳤고 + go2()부분은 반복적 DP로 바꿔서 풀어봤습니다.

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

string S;
bool DP[2505][2505];  
int DP2[2505];        // 최소 분할 횟수
#define INF 987654321
 
void fill_palindrome_dp() {
    int n = S.size();
    for (int i = 0; i < n; i++) {
        DP[i][i] = true;  
        if (i < n - 1 && S[i] == S[i + 1])
            DP[i][i + 1] = true;  
    }
 
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1; 
            DP[i][j] = S[i] == S[j] && DP[i + 1][j - 1];
        }
    }
}

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> S;
  
    fill_palindrome_dp();

    fill(DP2, DP2 + 2505, INF);
    DP2[0] = 0;  

    int n = S.size();
    for (int here = 0; here < n; here++) {
        if (DP[0][here]) {
            DP2[here] = 0; // 0부터 here까지 전체 부분 문자열이 팰린드롬이면 분할 필요 없음
        }
        for (int i = 0; i < here; i++) {
            if (DP[i + 1][here]) {
                DP2[here] = min(DP2[here], DP2[i] + 1); // 최소 분할 횟수 업뎃
            }
        }
    }

    cout << DP2[n - 1] + 1; // 문자열을 모두 팰린드롬으로 분할하기 위한 최소 횟수 + 1 출력

    return 0;
}

한번 이렇게 해보시겠어요?

중요한 주석 부분도 달아놓았습니다.

아 그리구 윽쓰님 ㅎㅎ

별점 5점 감사드립니다. ㅎㅎ

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

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

감사합니다.

강사 큰돌 올림.

윽쓰욱스

질문자

큰 도움이 되었습니다.

감사합니다. !!!

인프런 커뮤니티 질문&답변

7-S 시간초과 질문드립니다 !!