글 읽기 - 시간초과인데, 반례가 더 있을까요?..

amunre21 3년 전 0

decimal_list() 에서는 에라토스체로 100만까지의 소수를 구합니다.

goldbach()에서는 위에서 구한 소수들의 리스트와 입력값을 이용하여 맨처음 소수를 증가시켜가면서 (입력값-소수)값이 소수인지 비교하여 판별하구요.

이러면 에라토스테네스 체를 한번만 돌리는 것과 합이 n인 두 소수를 찾을때에도 p와 n-p의 탐색도 만족합니다.

그리고 goldbach()함수에서 조건에 만족하는 소수 쌍을 찾는순간 바로 반환해주기때문에 빠른 루프종료도 시도했습니다.

javascript에서 console.log로 제출을 하는데 반복문을 통한 console.log들은 시간이 오래 걸려서 answer 배열로 만들어서 줄바꿈기준으로 join시켰구요.

뭐가 문제일까요?..

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let input = [];

rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성    
  let max = 1000000;
  
  input.splice(-1,1);
  /*
  function getMaxOfArray(numArray) {
    return Math.max.apply(null, numArray);
  }
  let max = getMaxOfArray(input);  */
  let dec_list = decimal_list(max);
  let answer = [];  
  input.reduce((acc,cur,idx) => { 
    if(cur < 6 || cur > 1000000)  {
      answer.push("GoldBach's conjecture is worng.");
    }else{  
      answer.push(goldbach(dec_list, cur));
    }    
  },'');
  console.log(answer.join('\n'));  
  process.exit();
});

//input이 input보다 작은 소수들의 합으로 이루어지는지 판별 골드바흐 추측
function goldbach(list, input){
  let i = 0; 
  while(list[i]<=(input/2)){
    let j = input - list[i]; 
    if(list.indexOf(j)!=-1){
      return `${input} = ${list[i]} + ${j}`;
    }else{
      i++;
    }
  }
  return "GoldBach's conjecture is worng."
}

//input보다 작은 소수구하기
function decimal_list(n){
  let arr = Array(n+1).fill(true).fill(false, 0, 2);
    for(let i=2; i*i<=n; i++){
        if(arr[i]){
            for(let j=i*i; j<=n; j+=i){
                arr[j] = false;
            }
        }
    }
    let answer = [];
  arr.reduce((acc,cur,idx)=>{
    if(cur){
      answer.push(idx);
    }
  },'')
  return answer;
}

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

문제

문제

출처

ICPC

시간초과인데, 반례가 더 있을까요?..

amunre21 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말