글 읽기 - 6588번 도대체 왜 틀렸는지를 모르겠습니다. 도와주세요 ㅠㅠ

tmfrk0426 2년 전 0

C로 풀어봤습니다. 제가 아직 알고리즘을 배우지 않은 상태라 이렇게 밖에 작성 못하였지만 도대체 왜 틀렸는지 모르겠습니다.

시간초과도 해결했고, 다른 컴파일러로 돌려봐도 웬만한 예시 다 넣어도 출력값이 잘나옵니다. 혹시 어디가 틀렸는지 알려주실분 계신가요 ??ㅠㅠㅠ

#include <stdio.h>
#define MAX 100000
int result(int n);
int main (){
    int prime[MAX]={0};
    int m=0;
    for(int i=2;i<=MAX;i++)
    {
       
       if(result(i))
       {
           prime[m]=i;
           m++;
       }
    }
    int input;
    int a=0;
    int k;
    while(1)
    {
        a=0;
        scanf("%d",&input);
        if(input==0) break;
        for(k=0;k<m;k++)
        {
            for(int l=0;l<m;l++){
                    if((input-prime[k])==prime[l]){               
                    printf("%d = %d + %d\n",input,prime[k],prime[l]);
                        a=1;
                }
                if(a==1) break;
            }
            if(a==1) break;
        }
        if(a==0)
            printf("Goldbach's conjecture is wrong.");
    }   
    return 0;
}

 int result(int n){
     int i;
     for(i=2;i<n;i++)
     {
         if((n%i)==0)
             break;
     }
     if(i==n){
         return 1;
     }
     return 0;
 }

dbstmddbs4 2년 전 1

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

n은 백만까지인데

구한 소수가 10만까지기 때문에 틀렸습니다가 뜹니다.

tmfrk0426 2년 전 0

정말 감사합니다!!! 그래서 코드를 이렇게 바꾸어 보았습니다.

다른 컴파일러에서는 0.01s 걸리는 이 코드가 왜 아직도 시간초과가 나오는지 정말 모르겠습니다. ㅠㅠㅠ

#include <stdio.h>
#define MAX 1000000
int main (){
    int arr[MAX+1];
    for(int i=0;i<=MAX;i++)
        {
    	    arr[i]=i;
        }
    for(int a=2;a<=MAX;a++)
        {	
    	    if(arr[a]!=0)
    	        {
    		        for(int b=2;a*b<=MAX;b++)
    		        {
    			        arr[(a*b)]=0;
    		        }
    	        }
        }
    arr[1]=0;
    int prime[MAX];
    int m=0;
    for(int n;n<=MAX;n++)
    {
    	if(arr[n]!=0)
    	{
    		prime[m]=arr[n];
    		m++;
    	}
    }
    int input;
    int p=0;
    int k;
    while(1)
    {
        p=0;
        scanf("%d",&input);
        if(input==0) break;
        for(k=0;k<m;k++)
        {
            for(int l=0;l<m;l++){
                    if((input-prime[k])==prime[l]){               
                    printf("%d = %d + %d\n",input,prime[k],prime[l]);
                        p=1;
                }
                if(p==1) break;
            }
            if(p==1) break;
        }
        if(p==0)
            printf("Goldbach's conjecture is wrong.");
    }   
    return 0;
}

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

문제

문제

출처

ICPC

6588번 도대체 왜 틀렸는지를 모르겠습니다. 도와주세요 ㅠㅠ

tmfrk0426 2년 전 0

dbstmddbs4 2년 전 1

tmfrk0426 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말