<알고리즘 문제풀이&연습>/[C++] 백준, 프로그래머스 등등

[백준 9506] 약수들의 합

BlockDMask 2017. 10. 16. 15:00
반응형
  • 안녕하세요. 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 방법 -

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//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 == -1break;  //종료조건
 
        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() -1printf("+ ");
            }
            printf("\n");
 
        }else{
            printf("%d is NOT perfect.\n", n);
        }
 
    }
 
    return 0;
}
cs


- b 방법 -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//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*== n){   //a와 다른 부분 : 제곱을 하여 n이 되는 수 계산
        v.push_back(i);
        sum+=i;
    }
 
    return sum == n;
}
 
int main(void){
 
    int n;
    while(true){
        cin >> n;           //입력
        if(n == -1break;  //종료조건
 
        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() -1printf("+ ");
            }
            printf("\n");
 
        }else{
            printf("%d is NOT perfect.\n", n);
        }
 
    }
 
    return 0;
}
cs

4. 인증


- a 방법 -


- b 방법 -


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

감사합니다. 하트 꾹!

반응형