[백준 9506] 약수들의 합

• 안녕하세요. BlockDMask 입니다.

• 조금 간단한 문제를 풀어보았습니다.

• 약수들의 합을 구하는 문제 입니다.
  170907 문제 빼먹음 -> 171016 완료

0. 제목

• 백준 9506 약수들의 합

• BOJ 9506 약수들의 합

1. 문제 설명

n의 범위가 (2 < n < 100,000)인 어떤 수 n에 대해

숫자 n이 자신을 제외한 약수들의 합으로 나타내어 지면, 그 수를 '완벽한 수'라고 한다.

예를 들으 6은 6 = 1 + 2+ 3 이므로 완벽한 수이다.

n이 완벽한 수 인지 아닌지 판단해주는 프로그램을 작성하면 됩니다.

-- 입력 --

테스트 케이스마다 한 줄 간격으로 n 이 주어집니다. 입력이 마지막엔 -1 이 주어집니다.

-- 출력 --

테스트케이스 마다 한줄에 하나씩 출력해야합니다.

n이 완벽한 수라면, n 을 n이 아닌 약수들의 합으로 나타내서 출력합니다.

이 때, 약수들은 오름차순으로 나열하여 출력합니다.

n이 완벽한 수가 아니라면, n is NOT perfect. 를 출력합니다.

2. 풀이 과정

-a 방법 -

n이 주어지면

1 부터 n-1 까지 숫자들 중 

약수를 구하는

 전체 탐색 방법을 이용하여 문제를 풀었습니다.

- b 방법 -

약수는 제곱이 되어 자기자신이 되는 경우를 제외하고는

항상 짝을 이룹니다.

16을 예로 들면 [1,16] [2,8] [4] 이런식으로 존재합니다.

이런 방법을 이용하여 1 부터 제곱이 되어 n이 되는 수 전까지 i와 n/i 를 세줍니다.

a방법과는 다르게 b방법은 순서가 뒤죽박죽으로 들어가기 때문에

 sort 알고리즘을 이용하여 

오름차순으로 정렬해야합니다.

3. 코드

-a 방법 -

//https://www.acmicpc.net/problem/9506
//BOJ_9506_약수들의합
 
#include<iostream>
#include<vector>
#include<cstdio>
 
using namespace std;
 
bool Solution(vector<int>& v, int n){
    int sum=0;
    for(int i=1; i<n ; i++){    //약수 구하기 a
        if(n%i ==0){
            v.push_back(i);
            sum+=i;
        }
    }
 
    return sum == n;
}
 
int main(void){
 
    int n;
    while(true){
        cin >> n;           //입력
        if(n == -1) break;  //종료조건
 
        vector<int> v;
 
        if(Solution(v, n)){ //출력
            printf("%d = ", n);
            for(int i=0; i<v.size(); i++){
                printf("%d ", v[i]);
 
                if(i != v.size() -1) printf("+ ");
            }
            printf("\n");
 
        }else{
            printf("%d is NOT perfect.\n", n);
        }
 
    }
 
    return 0;
}

- b 방법 -

//https://www.acmicpc.net/problem/9506
//BOJ_9506_약수들의합
 
#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
 
bool Solution(vector<int>& v, int n){
    int sum=0;
    int i;
 
    for(i=1; i*i<n ; i++){    //약수 구하기 b : 쌍을 이루는 약수 구함
        if(n%i ==0){
            v.push_back(i);
            if(i>1) {
                v.push_back(n / i); //a와 다른점
                sum+=(n/i);
            }
            sum += i;
        }
    }
    if(i*i == n){   //a와 다른 부분 : 제곱을 하여 n이 되는 수 계산
        v.push_back(i);
        sum+=i;
    }
 
    return sum == n;
}
 
int main(void){
 
    int n;
    while(true){
        cin >> n;           //입력
        if(n == -1) break;  //종료조건
 
        vector<int> v;
 
        if(Solution(v, n)){ //출력
            sort(v.begin(), v.end()); //a방법과 다르게 b방법은 sort를 해주어야합니다.
 
            printf("%d = ", n);
            for(int i=0; i<v.size(); i++){
                printf("%d ", v[i]);
 
                if(i != v.size() -1) printf("+ ");
            }
            printf("\n");
 
        }else{
            printf("%d is NOT perfect.\n", n);
        }
 
    }
 
    return 0;
}

4. 인증

- a 방법 -

- b 방법 -

문제 출처 - https://www.acmicpc.net/problem/9506

감사합니다. 하트 꾹!