글 읽기 - java 시간초과 계속뜨는데 이유를 모르겠습니다..

dlwogns3413 2년 전 0

어디를 고쳐야 할까요.. 이 이상은 쟤 머리로는 시간을 줄일 방법이 생각이 안납니다..

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int rest = N;
    Loop: for(int i=2; i<=N; i++) {
      if(N == 1) break;
      int cnt = 0;
      for(int j=1; j<=Math.ceil(i/2); j++) {
        if(i % j == 0) cnt++;
        if(cnt > 1) break;
      }
      if(cnt == 1) {
        while(true) {
          if(rest % i != 0) break;
          if(rest == i) {
            System.out.println(i);
            break Loop;
          }
          rest = rest / i;
          System.out.println(i);
        }
      }
    }
  }
}

dldyddlwl 2년 전 1

아래에 있습니다.

/*
소인수분해(영어: prime factorization, integer factorization)는 1보다 큰 자연수를 
소인수(소수인 인수)들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는 방법을 말한다.
출처 : 위키피디아
*/

// 자, 아래의 코드를 함께 하나씩 확인해 봅시다!!

    int rest = N;
    Loop: for(int i=2; i<=N; i++) {    // N이 소수일 경우, 자기 자신이 약수이므로, i는 반드시 N까지 점검해야함
      if(N == 1) break; // 사실 이 부분은 없어도 됩니다. N이 1이라면 애초에 루프에 못들어오거든요! ( i = 2; i <= 1 ; i++)
      int cnt = 0;
        
        
      // 소수 점검 루프, 소인수는 소수인 인수이므로, i는 소수여야 함!!
      for(int j=1; j<=Math.ceil(i/2); j++) {
        if(i % j == 0) cnt++; // 약수 개수를 세봅니다.
        if(cnt > 1) break;    // 소수는 1과 자기자신만을 약수로 가지므로, 그 이외에는 break!
      }
        
        
      // 실질적인 rest 나누기 과정
      if(cnt == 1) {
        while(true) {
          if(rest % i != 0) break;    // 나누어 떨어지지 않으면 약수가 아니란 뜻이므로 break!!
          if(rest == i) {    // 만약에 남은 rest가 약수와 같다면, 더 이상 반복하지 않아도 됨! 바깥 루프 break!
            System.out.println(i);
            break Loop;
          }
          rest = rest / i;
          System.out.println(i);
        }
      }
    }

// 여기까지 봤을 때 어떤 과정이 시간을 잡아먹는다고 생각하시나요?
// 아래의 나누기 과정은 사실 말 그대로 나누기만 하기 때문에 별로 무거운 연산 과정은 아닙니다.
// 다행히 소인수분해 계산기라는 것이 있길래 문제의 최대 숫자인 1000만을 넣어봤는데요 2^7 * 5^7이 나오더군요
// 겨우 14번만 나누면 되는군요!

// 자, 그렇다면 남은 반복문은 무엇이죠? 네! 바로 소수인지 점검하는 파트죠.
// for 루프 j는 1부터 루트i까지 진행합니다.
// 이 루프는 i가 작을 때는 간단해보이지만 i가 커질수록, 이런 루프를 계속 도는 것은 꽤나 컴퓨터를 힘들게 할 것 처럼 보입니다.



// 그렇다면 여기서 여러가지 생각을 하게 됩니다. 
// 정말 많은 방법이 있을 것입니다. 하지만 여기서는 글이 너무 길어질 것을 막기 위해 한 가지 방법만 보고 갑시다! 

// 방법) 이 수가 소수인 지 일일이 확인하지 않고 넘어가는 방법
// 모든 자연수 X는, 수학의 무슨무슨 정리에 의해서, 
// 반드시 X = 2^a * 3^b * 5^c * ... 와 같은 소수들의 거듭제곱의 곱 형태로 전개됩니다. 
// (여기서, a b c ... 는 0 이상의 정수)

// 너무 당연해 보여서 사실 이걸 어떻게 이용해야할 지 감이 안 잡힙니다.
// 혹시 "에라토스테네스의 체" 라는 것을 알고 계신가요? ( 여백이 부족해서 구글에서 검색을 권장드립니다... )
// 작은 소수부터 소수들의 배수를 지워나가는 방법인데요. 이를 응용해볼 수 있습니다.


// 임의의 수 X에 대해서 가장 작은 소수 2부터 출발합시다.
// 이 X를 2로 최대한, 그러니까 더 이상 나누어 떨어지지 않을 때까지 나누어 봅시다.
// 그러면 이 나누어진 X의 전개식에서는 2의 거듭제곱이 모두 사라집니다.
// 이 전개식에는 자연스럽게 3 이상의 소수들만 남게 되죠.
// 그럼 이를 반복합니다. 마찬가지로 남은 수를 3으로 더 이상 나누어 떨어지지 않을 때까지 나눕니다.
// 그러면 3의 거듭제곱꼴이 모두 사라집니다.
// 이제 다음 수인, 4를 보려고 하니 4는 2의 배수잖아요? 이미 X는 2의 배수들을 모두 잃어버렸습니다. 따라서 4로 나눌 수가 없습니다.
// 그리고 마찬가지로 5도 진행합니다. 이를 N까지 쭉 반복합니다.


//
//
//
//
//
//
// 정말 모르겠으면 보기 ( 스포일러 주의!!)
//
//
//
//
//
//
//
//



for(int i =2;i*i<=n;i++){
        if(n%i==0){ // 나눌 수 있다면!
            // 출력
            n/=i; // 나누기
            i--; // 몇 제곱인지 모르므로 더 반복하기 위해 일부러 i에서 1 빼기 (그렇게 되면 i-- -> i++이 되어서 i가 유지됨)
        }
    }

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

문제

문제

출처

ICPC

java 시간초과 계속뜨는데 이유를 모르겠습니다..

dlwogns3413 2년 전 0

dldyddlwl 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말