-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
7-S 시간초과 질문드립니다 !!
24.04.18 02:07 작성 24.04.19 00:31 수정 조회수 55
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 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;
}
답변을 작성해보세요.
0
큰돌
지식공유자2024.04.19
안녕하세요 윽쓰님 ㅎㅎ
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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
답변 1