[C] 더블릿 4단계_ 소인수분해 문제
최근 중앙대학교 알고리즘 학술 동아리 CAULISM 기초반에 가입하였습니다. 과제로
1. 소인수분해 문제
자연수 n 이 입력으로 주어진다. 이 수를 소인수 분해하는 프로그램을 작성하시오.
입력 n 은 2 이상 1 000 000 000 이하의 자연수이다.
출력 소인수를 크기 순으로 공백을 사이에 두고 한 줄에 출력한다.
입출력 예
입력
20
출력
2 2 5
입력
7
출력
7와 최대수연결 문제가 과제로 나왔는데 두번째 문제는 내일 포스팅하도록 하겠습니다.
처음엔 간단하게 입력 받는 수 a와 2를 나머지연산하여 나눠떨어지면 출력하고, 그렇지
않으면 계속 1씩 더하면 되겠다!라고 생각하여 다음과 같이 코드를 짯습니다.
#include <stdio.h>
int main(){
int a, b = 2;
scanf("%d", &a);
while (a != 1){
if (a%b == 0){
printf("%d ", b);
a /= b;
}
else {
b++;
}
}
return 0;
}
이렇게하니 출력에는 전혀 문제가 없었지만 체점에서 96690과 같이 큰수가 여러번 들어가니 소인수 b를 1씩 올린다고 while문이 쓸데없이 너무 많이 돌아가 timeout이 뜨더군요ㅜㅜ 처음에 너무 쉽게 생각해서 여기서 맨붕ㅜㅜ 그래서 소인수를 어떻게 증가시키면 될까 하다가 20의 경우를 생각해보니
2 20
2 10
5 5
1
소인수 2에서 5로 증가하는 것은 2 + 5%2 이고 다른 경우에서도 성립할 것 같으니 소인수를
b += a %b라 하면 되겠다! 라고 생각하며 소인수의 증가를 확인할 printf와 함께 밑과 같이 수정하였지만
else {
b = b + a % b;
printf("\n b= %d \n", b);
}
94690의 소인수는 2, 5, 17, 557인데 이렇게 부정확하게 나오더라구요 ㅜㅜ
소인수를 하나하나 올려주자니 running time이 너무 길어지고, 다르게 표현하자니 정확한 표현 방법을 모르겠고 답이없는 상황이 되었습니다.ㅠ 그러나 몇십분동안 차근차근 생각해보니 소수는 2, 3에서만 1만큼 증가하고 3에서 5, 19에서 23과 같이 모두 2n(짝수)만큼 증가한다는 것을 깨달았습니다!!ㅋㅋㅋ 그래서 다음과 같이 코드를 수정하였습니다.
#include <stdio.h>
int main(){
int a, b = 2;
scanf("%d", &a);
while (a != 1){
if (a%b == 0){
printf("%d ", b);
a /= b;
}
else {
if (b == 2) b++;
else if (b > 2) b += 2;
}
}
return 0;
}
과연 실행 결과는???
핰 통과!!! ㅋㅋㅋㅋ 그렇게 어려운 문제는 아니였지만 부족한 실력으로 열심히 생각해서 나온 결과라 정말 기쁘더군요 ㅋㅋㅋㅋㅋㅋㅋ하하핳하
1번을 풀면서 코드를 간단하게 짜는 것도 좋지만 running time 생각하면서 좀 더 직관적으로 짜는게 좋을 수도 있다는 것과 문제가 안풀리면 아주 기초적인 단계부터 하나하나씩 예시들을 써보면 도움이 된다는 것을 깨달았습니당.
내일 최대수연결 문제도 힘내서 풀고 포스팅하겠습니다 오예~