글 읽기 - 반례좀 들어주세요

jry0827 4년 전 1

제가 스택을 쓰지않고 코드를 짰는데 런타임 에러가 나네요 반례좀 들어주세요

#include <iostream>
using namespace std;
int main(void)
{
    int a;
    bool in=false;
    int b[1000];
    int c[1000];
    cin>>a;
    for(int i=0; i<a; i++)
        cin>>b[i];
    for(int i=0; i<a; i++)
    {
        for(int j=i; j>0; j--)
        {
            if(b[j-1]>b[i])
            {
                c[i]=j;
                in=true;
                break;
            }
        }
        if(!in)
            c[i]=0;
        in=false;
    }
    for(int i=0; i<a; i++)
        cout<<c[i]<<endl;
    return 0;
}

seico75 4년 전 0

탑의 수는 500,000 이 최대입니다. 배열을 1000만 잡으면 런타임 에러가 날 것 같습니다.

jry0827 4년 전 0

배열을 500000으로 잡으니 시간 초과가 뜨는데 해결방법좀 주세요

seico75 4년 전 0

시간초과는 배열크기 때문이 아니라 배열크기가 커져서 입력이 커질때 런타임 에러가 안나니까 시간초과가 나는거는 아시죠?

입력이 1 2 3 4 5 6 7

이런 단조증가면 매번 이전 것을 다 뒤져서 O(N^2)정도 돌것 같습니다. 이경우 6에서 안걸러지면 5~1은 당연히 안 걸린다는 것을 이용하여 연산을 줄이면 될 것 같습니다. 그 방식이 스택류를 쓰면 좋을 것 같네요.

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

문제

문제

출처

ICPC

반례좀 들어주세요

jry0827 4년 전 1

seico75 4년 전 0

jry0827 4년 전 0

seico75 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말