[백준] 11653번 - 소인수분해

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

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

예제가 많은 것을 확인해볼 수 있는데,

여기서 N이 1인 경우에는 아무것도 출력하지 않으면 된다.

 

N=int(input())
S=2
while N>1:
    if N%S==0:
        N/=S
        print(S)
        continue
    S+=1

 

간단하게 이러한 코드를 작성하였는데,

해당 코드는 S에 1을 추가하면서 분해가 되는 즉,

나머지가 0이 되는 수에 대해서 출력하게 하였다.

 

이 코드의 문제점은 N의 값이 커지면 커질수록

S를 더하는 연산의 수가 많아지므로 시간제한에 걸릴 수 있다.

 

 

실제로 다음과 같이 풀긴 푸는데 찝찝한 느낌이 든다.

그럼 S라는 변수 없이 바로 출력하는 방법은 없을까?

 

N=int(input())
for i in range(2,int(N**(0.5))+2):
    while N%i==0:
        print(i)
        N//=i
if N!=1: print(N)

 

다음과 같이 범위를 N을 루트로 나눈 정수형에 2를 더하는

방법을 생각해볼 수 있다.

 

예를 들어서 72를 루트로 나눈 정수형에 2를 더하면 10이 되는데,

2부터 10까지 2를 72로 나누면 36,18,9 이렇게 총 3번이 반복된다.

그리고나서 9를 그 다음 i인 3으로 나누게 되면 3, 1이 되기 때문에

총 횟수 5번동안 2,2,2,3,3을 줄바꿈으로 출력하게 된다.

 

마지막 N이 1이 아닐때, 예제가 2또는 3처럼

N이 주어질때 해당 N을 출력하면 된다.

 

화이팅 💪