잘못 구현한 에라토스테네스의 체
1. 힌트
1) 주어진 코드를 곧이곧대로 구현하면 O ( N 2 ) O(N^2) O ( N 2 ) 의 시간 복잡도입니다.
2) 안쪽에 있는 for문을 n − 1 n - 1 n − 1 이하의 i i i 의 배수의 개수 + 1 + 1 + 1 로 이해할 수 있습니다.
3) n n n 이하의 i i i 의 배수의 개수는 ⌊ n i ⌋ \lfloor\displaystyle\frac{n}{i}\rfloor ⌊ i n ⌋ 로 나타낼 수 있고, 이 값은 O ( n ) O(\sqrt{n}) O ( n ) 종류의 값을 가집니다. 이를 O ( n ) O(\sqrt{n}) O ( n ) 시간에 반복하는 효율적인 방법이 존재합니다.
ahgus89님의 글 참조
2. 접근
1) 내가 문제를 푸는 과정을 수식화할 수 있을까?
안쪽 반복문의 j j j 를 나열하면 이와 같습니다.
1 , 1 + i , 1 + 2 i , 1 + 3 i . . . 1,\ 1+i,\ 1+2i,\ 1+3i... 1 , 1 + i , 1 + 2 i , 1 + 3 i . . .
j j j 는 계속 증가하다가 최대 n n n 까지 늘어날 것입니다. 수열의 모든 수에 1 1 1 을빼주면 이와 같습니다.
0 , i , 2 i , 3 i . . . 0,\ i,\ 2i,\ 3i... 0 , i , 2 i , 3 i . . .
맨 앞에 있는 0 0 0 만 빼고 생각하면 이 수열의 원소의 개수는 n n n 이하의 i i i 의 배수의 개수입니다. 이를 ⌊ n i ⌋ \lfloor\displaystyle\frac{n}{i}\rfloor ⌊ i n ⌋ 로 나타낼 수 있습니다.
2) 조화수열의 성질
a i = ⌊ n i ⌋ a_i = \lfloor\displaystyle\frac{n}{i}\rfloor a i = ⌊ i n ⌋ 이라고 정의해서 수열을 써볼 수 있습니다. 곧이 곧대로 1 1 1 부터 n n n 까지 반복하기엔 범위가 너무 큽니다. 우리는 a i a_i a i 의 값이 O ( n ) O(\sqrt{n}) O ( n ) 개의 서로 다른 종류만 가진다는 것에서 O ( n ) O(\sqrt{n}) O ( n ) 의 반복하는 방법이 있지 않을까 생각해 볼 수 있습니다. 자세한 설명은
ahgus89님의 글 참조
3. 구현
public class Main {
public static void main ( String [ ] args) throws IOException {
BufferedReader br = new BufferedReader ( new InputStreamReader ( System . in) ) ;
int N = Integer . parseInt ( br. readLine ( ) ) ;
int K = N - 1 ;
long sum = N ;
int j = 0 ;
for ( int i = 1 ; i <= K ; i = j + 1 ) {
j = K / ( K / i) ;
sum += ( long ) ( K / i) * ( j - i + 1 ) ;
}
System . out. println ( sum) ;
}
}
1) 시간 복잡도
반복문 하나이지만, O ( n ) O(\sqrt{n}) O ( n ) 개의 값에 대해서만 반복합니다.