11653 - 소인수분해

11653

기본 수학 2
소인수분해

• 말그대로 소인수분해를 하는 문제
• 1 입력시 출력 없음, 2부터는 입력시 소인수를 오름차순으로 출력

import java.util.Scanner;

public class bj11653_0122 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		for (int i = 2; i <= (int) Math.sqrt(N); i++) {
			if (primeTest(i) == false)
				continue;
			if (N % i != 0)
				continue;
			System.out.println(i);
			N = N / i;
			i = 1;
		}
		if (N != 1)
			System.out.println(N);

	}

	static boolean primeTest(int num) {
		if (num < 3) {
			return true;
		} else if (num % 2 != 0 && num > 2) {
			for (int i = 3; i <= (int) Math.sqrt(num); i += 2) {
				if (num % i != 0)
					continue;
				else
					return false;
			}
			return true;
		}
		return false;
	}
}

• 개인적으로 진짜 어려웠다.
• 험 실버5단계 문제긴한데 처음에 너무 만만하게 생각하고 냅다 코드 작성부터 시작해서 계속 막힌 것 같다.
• 처음엔 그냥 틀렸고, 시간초과를 두번 받았다. 그니까... 무작정 계속 1부터 검사해서 나눠지는 값을 찾는 게 정답이 아니란 뜻이다. 더 빠르게 하는 방법을 찾으라는 뜻...
• 이런 문제는 일단 어떻게 풀지 설계를 잘 하고 들어가는 게 맞는 것 같다. 그래서 종이에 논리회로를 대충 그려보고 시작했다.
• 일단... 소수판별 메서드가 필요하다. 그래서 boolean타입으로 primeTest메서드를 선언했고, 짝수는 어차피 소수가 아니니까 3부터 시작해서 2씩 늘려가며 나눈 나머지가 0인지 아닌지를 통해 소수를 판별했다. (true: 소수) (왜 필요한지는 아래에 있을 것)
• main으로 돌아와서, 수 N을 입력받고, N에 [2부터 시작해서 루트N까지] 나눠서 나머지를 구한다. 근데 그 [2부터 루트N까지]가 primeTest를 통과해야 나머지를 구하고, false반환시 continue한다. 즉 다음 수로 건너뛰어 다시 primeTest를 한다. 즉 primeTest를 통과한 [2부터 루트N까지]만 나눠서 나머지를 구한다는 뜻.
  • 왜 2부터냐? - 사실 3부터 해도 될 것 같다. 마지막에 언급하겠지만, (최종-1)회차 제출 때 1을 입력받은 경우를 고려하지 않아서 오류가 발생했다. 즉 1과 2의 경우를 특별하게 제외해주고 3부터 하는 식으로 바꿔도 무방할 것 같다...
  • 왜 루트N까지냐? - N이 2를 인수로 갖지 않는다면, N/2 이상의 인수는 당연히 갖지 않는다. 또, N이 3을 인수로 갖지 않는다면, N/3 이상의 인수는 당연히 갖지 않는다. 계속 숫자를 올려갈 수록, N이 갖지 못하는 인수의 최대값도 점점 낮아진다. 그러다 루트N까지 가게 된다면, "N이 루트N을 인수로 갖지 않는다면, N/루트N = 루트N 이상의 인수는 당연히 갖지 않는다."가 된다. 따라서 N이 가질 수 있는 최대의 인수 값은 루트N이다. (루트N이 int로 존재한다면)
• 중요한건... for문이 어떻게 반복되고 어떻게 종료되는가 이다. for안에 첫 if는 primeTest를 통과해야 나눠서 나머지를 구할 자격이 주어진단 의미이고, 두 번째 if는, 그래서 나눈 나머지가 0이 아니라면? 다음 숫자로 다시 primeTest부터 하라는 뜻이고, 두 if에 모두 안걸렸다는 것은 primeTest를 통과한 소수이며 && N에 나눈 나머지가 0이란 뜻이니까, 소수면서 인수다, 즉 소인수다. 심지어 현존 가장 작은 소인수이다(오름차순도 만족). 그러면 당장 그 수 i를 출력하고... 다시 for문을 돌게 하고 싶은데, 똑같이 돌면 안되고 i는 다시 2로 낮춰야 한다. (for문이 continue되면 i가 ++되니 i=1을 넣어주는 게 맞다) 그리고 N도 이미 가장 작은 소인수로 나눠졌으니 적용시켜야 한다. N=N/i;
• 그리고 마지막으로 for문이 돌아갈 때, (즉 2부터 당시 루트N까지 다 돌면서 primeTest를 통과한 것들이 모두 N에 나눈 나머지가 0인 게 없다면?) (지금 생각해보니까 그게 primeTest랑 똑같네... 암튼) for문을 종료하고 그 N을 출력하면 된다.
  • 근데 왜 if가 있냐? 1인 경우에는 출력을 하지 말라했으니까 마지막에 급하게 첨가했다.
    • 왜냐면 if를 안넣고 돌렸다가 "채점중(99%)" 에서 "틀렸습니다!"가 떠서 5초간 좌절감을 맛봤기 때문... 하지만 if를 넣고 맞았다.
• 어려웠다. 근데 재밌었다...

 

채점되는 순간의 떨림...