양의 정수 N이 주어졌을 때, N을 0으로 만들기 위해 필요한 연산 횟수를 구하는 것이 이 문제의 목표입니다. 여기서 적용되는 연산은 N = N - P이며, P는 N의 가장 작은 소인수(최소 소인수)입니다.
예제로 이해하기
입력 − N = 17
출력 − N을 0으로 줄이는 데 필요한 연산 횟수: 1
설명 − 17의 최소 소인수는 17 자신입니다. 따라서 연산은 단 한 번만 적용됩니다. 즉, 17 - 17 = 0이 됩니다.
입력 − N = 20
출력 − N을 0으로 줄이는 데 필요한 연산 횟수: 10
설명 − 20의 최소 소인수는 2입니다. 2를 계속 빼면서 다음 소인수를 찾는 과정은 다음과 같습니다.
20 % 2 == 0, 20 - 2 = 18 18 % 2 == 0, 18 - 2 = 16 ……14, 12, 10, 8, 6, 4, 2, 0 총 10번의 연산이 적용됩니다.
프로그램에 사용된 접근 방식
모든 짝수 N에 대해 최소 소인수는 항상 2이며, 짝수에서 2를 빼면 결과 역시 짝수가 됩니다. 반면 모든 홀수의 최소 소인수는 홀수이고, 홀수에서 홀수를 빼면 짝수가 되므로 이후에는 다시 2가 최소 소인수가 됩니다.
최소 소인수를 찾으려면 i = 2부터 시작하여 i * i < N이면서 N % i == 0을 만족하는 i까지 탐색합니다. 이때 총 연산 횟수는 count = 1 + (N - i) / 2로 계산할 수 있습니다.
알고리즘 단계
정수 N을 입력으로 받습니다.
함수 N_to_Zero(int N)은 N을 받아 N을 0으로 줄이는 데 필요한 연산 횟수를 반환합니다.
count의 초기값을 0으로 설정합니다.
i = 2부터 시작하여 (i * i) < N이면서 N이 i로 나누어 떨어지지 않는 동안(N % i != 0) i를 증가시키며 순회합니다.
(i * i)가 N을 초과하면 i = N으로 설정합니다. 이는 N이 소수임을 의미합니다.
연산 횟수는 1 + (N - i) / 2입니다.
count를 1 + (N - i) / 2로 설정합니다.
count를 결과로 반환합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
int N_to_Zero(int N){
int count = 0;
int i = 2;
while((i * i) < N && (N % i)){
i++;
}
if((i * i) > N){
i = N;
}
count = 1 + (N-i)/2;
return count;
}
int main(){
int N = 10;
cout<<"N을 0으로 줄이는 데 필요한 연산 횟수: "<<N_to_Zero(N);
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
N을 0으로 줄이는 데 필요한 연산 횟수: 5