글 읽기 - 배열로 스택 구현에서 에러.

amatuer789 5년 전 0

스택으로는 정답처리 되었는데, 배열로 하니 자꾸 오답이 나서 질문드립니다.

하단 코드(정답 처리)는 테스트 용이라, 스택과 배열이 모두 사용되고 있습니다.

문제되는 부분은 Line 15,16 으로 하단 코드를 다음과 같이 변형하면, 오답처리가 됩니다.

int s = S[idx];

int len = L[idx];

배열로 스택처리를 구현하려 했는데, 혹시 실수한 부분이 있는지 확인 부탁드리겠습니다.

#include <cstdio>
#include <stack>
using namespace std;
int A[2002], dp[2001][2001];
int S[2002], L[2002];
int main(){
    int n, m, s, e, idx = -1;
    scanf("%d", &n);
    stack<pair<int, int>> st;
    for(int i = 1; i <= n; i++)
        scanf("%d", &A[i]), st.push({i,1}), S[++idx] = i, L[idx] = 1;
    for(int i = 1; i <= n-1; i++)
        if(A[i] == A[i+1]) st.push({i,2}), S[++idx] = i, L[idx] = 2;
    while(idx >= 0){
        int s = st.top().first
        int len = st.top().second;
        st.pop();
        idx--;
        dp[s][s+len-1] = 1;
        if(s-1 > 0 && s+len <=n && A[s-1]==A[s+len]) S[++idx] = s-1, L[idx] = len+2, st.push({s-1, len+2});
    }
    scanf("%d", &m);
    while(m--){
        scanf("%d%d", &s, &e);
        printf("%d\n", dp[s][e]);
    }
}

BaaaaaaaaaaarkingDog 5년 전 1

스택에 원소가 최대 몇개까지 들어갈지 고민해보시면 문제점이 보일거에요

amatuer789 5년 전 0

아 .. 감사합니다 ...ㅎㅎ

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

문제

문제

출처

ICPC

배열로 스택 구현에서 에러.

amatuer789 5년 전 0

BaaaaaaaaaaarkingDog 5년 전 1

amatuer789 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말