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를 넣고 맞았다.
- 근데 왜 if가 있냐? 1인 경우에는 출력을 하지 말라했으니까 마지막에 급하게 첨가했다.
- 어려웠다. 근데 재밌었다...
채점되는 순간의 떨림...
'PS - BOJ' 카테고리의 다른 글
1138 - 한 줄로 서기, 1032 - 명령 프롬프트 (0) | 2022.01.23 |
---|---|
1124 - 언더프라임 (0) | 2022.01.23 |
10872 - 팩토리얼, 1065 - 한수 (0) | 2022.01.22 |
11729 - 하노이 탑 이동 순서 (빠른 입출력!!) (0) | 2022.01.22 |
8958 - OX퀴즈, 1712 - 손익분기점 (0) | 2022.01.22 |