[백준] 9506번 : 약수들의 합 | C++

1. 문제 상세

 

https://www.acmicpc.net/problem/9506

 

 

 

2. 문제 접근

 

완전수를 구하기 위해 입력받은 자연수 N 을 1부터 N / 2 의 수로 나누어보며 나눈 나머지가 0이 되는 경우의 수를 배열에 추가하고, N 과 비교할 완전수 변수에 더해준다.

 

모든 약수들을 확인하고 나면 입력받은 N 과 약수들을 모두 더해둔 값이 저장된 완전수 변수의 값이 같은지 확인한다.

값이 같다면 완전수이므로 배열에 추가해둔 약수들로 조건대로 출력하고, 아닌 경우도 해당 조건대로 출력한다.

 

 

 

3. 문제 풀이

 

#include <iostream>
using namespace std;

int main() {
    int n, factor[50000];
    
    while(true) {
        int perfect = 0, index = 0;
        
        cin >> n;
        
        if(n == -1) break;
        
        for(int i = 1; i <= n / 2; i++) {
            if(n % i == 0) {
                perfect += i;
                factor[index++] = i;
            }
        }
        
        if(perfect == n) {
            cout << n << " = ";
            for(int i = 0; i < index - 1; i++) cout << factor[i] << " + ";
            cout << factor[index - 1] << endl;
        }
        else cout << n << " is NOT perfect." << endl;
    }
}

 

정수형 변수 n 과 크기가 50000인 배열 factor 를 선언한다.

 

while문에 조건을 true 로 주어 무한 반복하도록 한다.

정수형 변수 perfect 와 index 를 선언하고 각각 0으로 초기화한다.

 

 cin 으로 정수를 입력받아 n 에 저장한다.

 

if문으로 n 이 -1이라면 break 로 반복을 빠져나간다.

 

for문으로 i 가 1부터 n / 2 보다 작거나 같을 때 1씩 더하며 반복하도록 한다.

반복에서는 if문으로 n 을 i 로 나눈 나머지가 0인 경우 perfect 변수에 i 의 값을 더해주고,

factor 배열의 index 번 인덱스의 값에 i 를 저장, index 의 값을 1증가시킨다.

 

반복이 끝나면 if문으로 perfect 와 n 이 같은지 확인, 같다면 cout 으로 n 과 " = " 을 출력한다.

for문으로 i 가 0부터 index - 1 보다 작을 때 1씩 더하며 반복하도록 하고,

반복에서는 factor 배열의 i 번 인덱스의 값과 " + " 를 출력한다.

반복이 끝나면 factor 배열의 index - 1 번 인덱스의 값을 출력한다.

 

perfect 와 n 의 값이 다르다면 n 과 " is NOT perfect." 를 출력한다.

 

 

 

4. 성능 확인

 

 

 

 

5. 마무리

 

.