BOJ 4673 셀프 넘버

1 개요

BOJ 4673 셀프 넘버

• 자연수 n에 대해 d(n)의 값을 구하는 함수를 정의해 문제를 해결해봅니다
• 알고리즘 분류: 에라토스테네스의 체, 입문용

2 Bash

동작은 하지만 성능 문제가 있음.

LANG=C
SELF_NUMBERS=""

for i in `seq 1 10000`
do
        if [ ! `echo "$SELF_NUMBERS" | grep -cP " ${i} "` -ne 0 ]; then
                echo $i
        fi
        k=`echo $i | perl -pe 's/(\d)/$1 + /g'`
        i=`expr $i + ${k}0`
        SELF_NUMBERS="${SELF_NUMBERS} ${i} "
done

3 C++

#include <iostream>
using namespace std;
#define SIZE 10000
int main() {
    int d, temp;
    bool a[SIZE+1]={};
    for(int i=1;i<=SIZE;i++) {
    	temp=i;
    	d=i;
        while(temp){
    	    d += temp%10;
    	    temp /= 10;
    	}
    	if(d<=SIZE) a[d]=true;
    }
    for(int i=1;i<=SIZE;i++) {
    	if( !a[i] ) printf("%d\n", i);
    }
}

#include <iostream>
using namespace std;
#define SIZE 10000
bool a[SIZE+1]={};
int d(int n) {
	int temp = n;
	int res = n;
    while(temp){
	    res += temp%10;
	    temp /= 10;
	}
	return res;
}
int main() {
    int temp;
    for(int i=1;i<=SIZE;i++) {
    	if( !a[i] ) printf("%d\n", i);
    	temp = d(i);
    	if( temp<=SIZE ) a[temp] = true;
    }
}

4 Java

public class Main {
    private static final int SIZE = 10000;
    private static boolean[] flags = new boolean[SIZE+1];
    private static int d(int n) {
        int result = n;
        char[] digits = String.valueOf(n).toCharArray();
        for( int i=0; i<digits.length; i++ ) {
            result += digits[i] - '0';
        }
        return result;
    }
    public static void main(String args[]) {
        int temp;
        for(int i=1; i<=SIZE; i++) {
            if( !flags[i] ) System.out.println(i);
            temp = d(i);
            if( temp <= SIZE ) flags[temp] = true;
        }
    }
}

5 Perl

use List::Util qw(sum);
@self_numbers = ();
for $i (1..10000) {
    print "$i\n" unless ($self_numbers[$i]);
    $v=$i + sum(split //, $i);
    $self_numbers[$v]=1;
}

6 PHP

<?php
function d($n) { return $n + array_sum(str_split($n)); }
$self_numbers = [];
for($i=1; $i<=10000; $i++) {
    if( !array_key_exists($i,$self_numbers) ) echo $i . "\n";
    $self_numbers[d($i)] = 1;
}

7 Python

def d(n):
    return n + sum(map(int,list(str(n))))
self_numbers = {}
for i in range(1,10001):
    if i not in self_numbers:
        print( i )
    self_numbers[d(i)] = 1

8 같이 보기

• 셀프 넘버
• 에라토스테네스의 체
• 함수 str_split()
• 함수 array_key_exists()

9 참고

• http://poj.org/problem?id=1316