글 읽기 - 10610 질문드려요

resolution15 8년 전 0

시간초과가 뜨네요,, 어느부분에서 시간초과가 뜨는지 모르겠습니다.

#include <stdio.h>
#include <string.h>

char a[100004];

int main()
{
    long long int len=0;
    int ans=0;
    int zero_location=0;
    int max=0;
    int max_location=0;
    
    
    scanf("%s",a);
    len=strlen(a);
    
    for(int i=0;i<len;i++)
    {
        ans+=a[i]-48;
        if(a[i]=='0')
            zero_location=i;
    }
    
    if(ans %3 == 0 && zero_location != 0)
    {
        for(int k=0;k<len;k++)
        {
            for(int j=0;j<len;j++)
            {
                if(j!=zero_location && a[j]-48>max)
                {
                    max=a[j]-48;
                    max_location=j;
                    if(max==9)
                        break;
                }
            }
            printf("%d",max);
            a[max_location]=0;
            max=0;
            max_location=0;
        }
        printf("\n");
    }
    else
        printf("-1\n");
    return 0;
}

baactree 8년 전 1

len=10^5

O(len^2)으로 풀어서 시간초과아닐까요?

resolution15 8년 전 0

감사합니다!시간복잡도가 n^2이였군요!

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

문제

문제

출처

ICPC

10610 질문드려요

resolution15 8년 전 0

baactree 8년 전 1

resolution15 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말