[백준] 11653번 소인수분해 - 결과 포함

[참고]https://www.acmicpc.net/problem/11653

11653번: 소인수분해

정수를 소인수분해하는 프로그램을 작성하는 문제였다.

처음에는 단순하게 소인수분해를 하는 과정을 그대로 프로그래밍했다.

정수를 입력받고 2부터 정수까지 나누어 떨어지면 그 피연산자를 출력하고 나누어 떨어지지 않으면 피연산자를 증가시키는 형태였다.

그러나 처음에는 "시간초과"가 뜨면서 실패했다.

 

두 번째 시도하면서 여러 가지 고민을 했다. 시간이 초과가 된 이유는 아마 반복문에 있을 것이다.

무한루프에 빠지는 경우의 수가 있거나 출제자가 의도한 대로 하지 않아 나누어보지 않아도 되는 경우에도 반복문에 들어간 것이라고 예상했다.

 

소인수분해의 정의에 대해 생각해봤지만 쉽게 떠오르지 않았다. 첫 번째 코드의 반복문은 2부터 계속 시도하다가 나누어 떨어지면

다시 2로 돌아와서 처음부터 다시 2부터 나누어 보기 때문에 많은 수행을 할 것으로 보이긴 했다.

테스트 케이스 예제로 나온 "9991"이라는 숫자에 주목했다. 다른 숫자들은 2나 3으로 나누어 졌지만 9991은 97과 103이 나왔다.

 

반복문을 생각해보면 2부터 97까지 나누다가 97로 나누어 떨어지고 다시 2부터 102까지 나누어보다가 103이 되자 나누어 떨어지기 때문에 출력하고 반복문이 끝나는 흐름이었다. 103까지 가보지 않고 나누어 떨어지는 수가 있을지 확인해야 했다.

 

생각을 해보니 9991을 97로 나누었을 때 몫은 103이었다. 97은 103보다 작다. 그렇기 때문에 103까지 가지 않고 97에서 끝난 것이다.

즉, 나누었을 때 몫이 나누는 수보다 작은 경우는 없을 것이었다. 왜냐하면 그러기 전에 이미 시도했을 것이기 때문이다. 103을 시도하기 전에 97을 시도한 것처럼 말이다. 그럼 어느 숫자부터 몫이 나누는 수보다 작아지는지 기준을 정해야 했다.

 

결과적으로 제곱을 이용하면 끝까지 돌지 않고 반복문을 끝낼 수 있었다. 만약 나누는 수의 제곱이 나누어지는 수보다 크다면 당연히 그 몫은 나누는 수보다 작을 것이다. 위에서 말했듯이 그 몫은 이미 이전에 시도했을 것이다. 마치 구구단에서 8 X 9 = 72 와 9 X 8 =72가 같은 것처럼 같은 시도를 똑같이 두 번하고 있었던 것이다.

 

[전체 소스 코드]

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    cin.tie(NULL);
    cin.sync_with_stdio(false);

    int N;
    int operand = 2;

    cin >> N;

    while (N > 1)
    {
        if (N % operand == 0)
        {
            cout << operand << '\n';
            N /= operand;
            operand = 2;
        }
        else
        {
            operand++;
            if (operand * operand > N)
            {
                cout << N << '\n';
                break;
            }
        }
    }
}