백준 - 9506번 약수들의 합(수학, 구현)

문제

어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다.

예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다.
n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라.

입력

입력은 테스트 케이스마다 한 줄 간격으로 n이 주어진다. (2 < n < 100,000)
입력의 마지막엔 -1이 주어진다.

출력

테스트케이스 마다 한줄에 하나씩 출력해야 한다.
n이 완전수라면, n을 n이 아닌 약수들의 합으로 나타내어 출력한다(예제 출력 참고).

이때, 약수들은 오름차순으로 나열해야 한다.
n이 완전수가 아니라면 n is NOT perfect. 를 출력한다.

C++ 풀이

고정된 최대 길이의 배열을 정의하여, 해당 배열에 약수들을 차례로 저장하고, 합계를 계산하여 최종 모든 약수를 찾았을 때 완전수를 확인하고 출력하는 방식으로 풀이 하였다. 다시 말하자면, 무지성으로 구현한 풀이!😲

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int n, tot, arr[100000]={0,},j,k=0; 
    // n은 입력, tot:약수의 합, arr ~ 약수 모음배열, j:arr의 인덱스,k: 출력시 활용
    while(cin>>n){
        if (n==-1) break; // -1이면 끝
        tot=0; // 개별 n마다 0으로 초기화
        j=0;   // 개별 n마다 약수모음배열의 인덱스 초기화
        for(int i=1; i<n; i++){
            if (!(n%i)) { // 약수이면
                tot += i; 
                arr[j++]=i;
            }
        }
        if (tot==n) { // 완전수이면
            printf("%d = ", n);
            k=0;
            while(j--){ // j=0 즉 약수의 개수만큼 순회
                j?printf("%d + ", arr[k++]):printf("%d\n", arr[k++]);
                // 삼항연산자로 j가 마지막 약수인 경우 출력 예외 처리
            }
        }
        else
            printf("%d is NOT perfect.\n",n);
    }
    
    return 0;
}

숏코딩 분석하기

10만 이하의 완전수가 이거밖에 없어?

10만 이하의 완전 수는 아래 정답과 같이 4개밖에 없다는 사실..

#include <iostream>
using namespace std;

int main() {
	int n;
	while(cin>>n&&n>0) {
		if(n==6||n==28||n==496||n==8128) {
			printf("%d = 1",n);
			for(int i=2;i<=n/2;i++) if(n%i==0) printf(" + %d",i);
			printf("\n");
		}
		else printf("%d is NOT perfect.\n",n);
	}
}

vector로 동적할당하기

#include<iostream>
#include<vector>
using namespace std;
vector<int>V,tmp;
int main(){
	int n,cnt,i;
    while(cin>>n&&n+1){
    	V=tmp;cnt=0;
        for(i=1;i<=n/2;i++){
        	if(n%i==0){
            	cnt+=i;
                V.push_back(i);
            }
        }
        cout << n;
        if(n==cnt){
        	cout<<" = "<<V[0];
            for(i=1;i<V.size();i++)
            	cout<<" + "<<V[i];
        }
        else cout<<" is NOT perfect.";cout<<"\n";
        }
}