백준 23822번: 서로소 그래프 (JAVA)

문제

우석이는 심심할 때마다 그래프를 그린다. 우석이는 매달 새로운 그래프를 그리는데, 이번 달에는 서로소 그래프를 그린다.

서로소 그래프는 1부터 N까지의 번호를 가진 N 개의 정점으로 이루어져 있으며, 서로 다른 두 정점의 번호가 서로소일 때만 두 정점이 간선 하나로 직접 연결되어 있다.

우석이는 간선을 얼마나 많이 그려야할지 궁금해졌다. 정점의 개수 N이 주어질 때, 만들어야 하는 간선의 개수를 알려주자.

입력

첫째 줄에 그래프의 정점 개수 N이 주어진다.

출력

우석이가 그려야하는 간선의 수를 출력한다.

제한

•  1≤N≤50000 

 

---

 

풀이

임의의 자연수 N에 대하여, N보다 작은 수 중 N과 서로소인 수의 개수는 phi(N) (phi: Euler's phi function) 개이다.

주어진 문제를 살펴보면, 임의의 N과 N보다 작은 모든 K 사이에는 총 phi(N)개가 생긴다. 즉, 정점의 개수가 N개라면 sigma(phi(i)) (1<= i <=N)을 구하면 된다. 숫자마다 소인수분해한 후 phi function 값을 계산하여 더하는 대신, N+1 길이의 int[]를 선언한 후, 각 index에 index값을 넣은 후 소수에 대하여 for문 돌리면서 그 수로 나눠지면 (p-1)*p를 값에 곱해주면 된다. 

Euler's phi function의 설명은 https://en.wikipedia.org/wiki/Euler%27s_totient_function 참고.

 

 

스스로 배운 점

• 문제를 본 후, 조깅하면서 문제 풀이 방법을 생각하면서 'overflow'가 발생하지 않을 거야!' 라고 확신을 가진 후 코드를 짰다. 몇 번의 시행착오 후 다시 천천히 살펴보니 50000 근처 값에서는 21억 이상의 값이 나오면서 overflow가 발생한다. 고정관념을 뒤집기가 힘들다보니, 수정하는데 시간이 오래 걸렸다. JAVA로 코드를 짤 때엔 overflow에 대해 항상 조심하고 또 조심하자.
• 에라토스테네스 체 구현할 때 루트n까지만 for문을 돌리면 되긴 하는데, 이 짓 하다가 구현 꼬인게 한두번이 아니다. 어차피 asymptotical한 관점에선 똑같으니(에라토스테네스 체: O(NloglogN)) 그냥 n까지 for문 돌리자

 

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		boolean[] isPrimeNumber = new boolean[n+1];
		Arrays.fill(isPrimeNumber, true);
		isPrimeNumber[0] = isPrimeNumber[1] = false;
		for (int i = 2; i<n+1; i++) {
			if (isPrimeNumber[i]) {
				for (int j = 2 * i; j < n+1; j += i) {
					isPrimeNumber[j] = false;
				}
			}
		}
		List<Integer> primeList = new ArrayList<Integer>();
		for (int i = 0; i < n+1; i++) {
			if (isPrimeNumber[i]) {
				primeList.add(i);
			}
		}
		int[] intArray = new int[n+1];
		for (int i = 1; i < n+1; i++) {
			intArray[i] = i;
		}
		intArray[1] = 0;
		
		for (int p: primeList) {
			for (int i = p; i < n+1; i += p) {
				intArray[i] = intArray[i] / p * (p-1); //overflow 피하기 위해 순서를 바꿈
			}
		}
		
		int sum = 0;
		for (int i = 1; i < n+1; i++) {
			sum += intArray[i];
		}
		System.out.println(sum);
	}
	
	
}

 

잡담

https://gall.dcinside.com/mgallery/board/view/?id=ps&no=18190&exception_mode=recommend&page=1 : O(1) 풀이... 이 글을 통해 이 문제를 접하게 되었다.