글 읽기 - C# 시간 초과를 해결할 방법을 모르겠습니다.

craft_roder 3년 전 0

이 식대로 진행하면 괜찮을거라 생각했는데

for문 안에 while문이 돌아서 그런건지 for문 안에서 다른 함수를 계속 부르고 있어서 그런건지

아예 저 식이 잘못되서 다른 알고리즘으로 풀어야 하는지 잘 모르겠습니다.

using System;
using System.Text;
using static System.Console;

namespace Baekjoon_Practice
{
    class Solution
    {
        public static void Main()
        {
            int N = Convert.ToInt32(ReadLine());
            if (N == 1) { return; } // N이 1일 경우 아무것도 출력 X
            StringBuilder PrimeGroup = new StringBuilder();
            int currentN = N;

            for(int i = 2; i <= N; i++)
            {
                if (currentN <= 1) { break; }
                if (!IsPrimeNum(i)) { continue; }
                while(currentN/i != 0 && currentN%i==0)
                {
                    PrimeGroup.Append(i + "\n");
                    currentN = currentN/i;
                }
            }

            Write(PrimeGroup);
            return;
        }

        public static bool IsPrimeNum(int temp)
        {
            for (int i = 2; i < temp; i++)
            {
                if (i == temp) { continue; }
                if (temp % i == 0)
                {
                    return false;
                }
            }

            return true;
        }
    }
}

slah007 3년 전 1

isPrime이 O(i)번이고 2<=i<=N이라면 O(N^2)번의 연산이 필요합니다.

소수를 미리 판정해 두거나, 어떤 수 N을 나누는 가장 작은 수는 소수라는 성질을 이용해보세요.

craft_roder 3년 전 0

아 복잡도가 꽤 많이 나가는 연산이였군요..

감사합니다!

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

문제

문제

출처

ICPC

C# 시간 초과를 해결할 방법을 모르겠습니다.

craft_roder 3년 전 0

slah007 3년 전 1

craft_roder 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말