글 읽기 - 문제의 본래 의도가 DP로 풀어야만 하는 건가요??

ababc1005 2년 전 0

문제에 주어진 입력 범위들을 처음 봤을 때

그냥 수열의 각 숫자들을 중심으로 펠린드롬이 최대 반지름 얼마까지 뻗는지 확인하고 (O(N^2) = 4,000,000)

map에 {index, radius} 형태로 데이터를 저장한 다음,

들어오는 질문들에 대해서 map에서 바로바로 뽑아서 확인하면 되지 않을까? (O(M*logN) = 20,000,000)

해서 풀었는데 250ms 내외로 AC가 나왔습니다.

풀고 나서 분류된 문제 유형과 게시판 확인해보니 많은 분들이 DP로 푸셨던데

지금 DP 풀이는 고민하는 중입니다만, 그냥 언뜻 생각하기에

본래 문제 의도가 DP라면 N을 10,000정도 늘리도록 요청하는게 나을거 같아서

본래 문제 의도는 무엇이었을까? 싶어서 궁금해서 글 올려봅니다.

#include<iostream>
#include<map>

using namespace std;

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

    int N;
    cin >> N;
    int seq[N];
    for(int i = 0; i < N; i ++){
        cin >> seq[i];
    }

    map<int, int> m;

    for(int i = 0; i < 2*N-1; i ++){
        if(i % 2 == 0){
            int index = i / 2;
            int radius = 0;
            while(index - radius >= 0 && index + radius < N){
                if(seq[index-radius] != seq[index+radius]){
                    radius --;
                    break;
                }
                radius ++;
            }
            m.insert({i, radius});
        }else{
            int index = i;
            int radius = 0;
            while(index/2 - radius >= 0 && index/2 + 1 + radius < N){
                if(seq[index/2 - radius] != seq[index/2 + 1 + radius]) break;
                radius ++;
            }
            m.insert({i, radius});
        }
    }

    int M;
    cin >> M;
    for(int i = 0; i < M; i ++){
        int S, E;
        cin >> S >> E;
        S --;
        E --;
        if((S + E) % 2 == 0){
            int center = (S+E)/2;
            int radius = m.find(S+E) -> second;

            if(center - radius <= S) cout << 1 << '\n';
            else cout << 0 << '\n';
        }else{
            int index = S+E;
            int radius = m.find(index) -> second;

            if(index/2 - radius < S) cout << 1 << '\n';
            else cout << 0 << '\n';
        }

    }
    return 0;
}

djm03178 2년 전 0

DP 풀이가 메모리를 O(N^2)을 쓰기 때문에 많이 늘리기는 어렵습니다. 시간 복잡도도 O(N^2+M)으로 작성하신 풀이와 크게 다르지 않고, 오히려 dp보다 더 생각하기 어려운 풀이가 아닐까 싶습니다.

djm03178 2년 전 0

사실 map 대신에 일반 배열에 답을 저장하시면 이 코드의 시간 복잡도도 O(N^2+M)이 됩니다.

sonjaewon 2년 전 1

dp[L][R] : S[L ... R] 이 팰린드롬인가?

로 하면 될것 같습니다.

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

문제

문제

출처

ICPC

문제의 본래 의도가 DP로 풀어야만 하는 건가요??

ababc1005 2년 전 0

djm03178 2년 전 0

djm03178 2년 전 0

sonjaewon 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말