[구현/수학] 백준 4673 셀프 넘버 - Python, Java

 

[ Contents ]

 

 

1. 문제 (링크 참조)

4673번: 셀프 넘버

 

 

 

2. 문제 풀이

 10000이하의 셀프 넘버를 출력하는 문제입니다. 셀프 넘버의 규칙은 다음과 같습니다.

생성자 d(n): 자기 자신(n)과 각 자리수를 더한 수
Self Number: 생성자가 없는 수

 

 

2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학

[Algorithm] 단골 1번 문제, 구현 / 수학

 1부터 10000까지 생성자를 구하여, 셀프 넘버가 아닌 것을 소거해나가는 문제입니다. 소수를 구하는 에네토스 테네스의 체와 비슷한 방식입니다. 

 

 

 

3. 코드

def selfNumber(n):
    res = n
    #각 자릿수 더하기
    while n != 0:
        res += n%10
        n //= 10
    return res

 먼저, selfNumber를 구하는 함수를 정의합니다. 위 공식대로, 자기 자신과 각 자리수를 더합니다.

 

 

number = [0]*10001
for i in range(10001):
    # 생성자 계산
    d = selfNumber(i)
    if d < 10001:
        number[d] += 1
        
    # 셀프넘버 출력
    if number[i] == 0:
        print(i)

 0~10000까지의 리스트를 0으로 초기화합니다. 셀프넘버인지 아닌지를 판별하는 체크리스트로 사용됩니다.

 0부터 10000까지 반복문을 돌면서, 계산된 생성자와 같은 숫자는 셀프넘버에서 제외합니다. 자기 차례가 될 때까지, 셀프넘버에서 제외되지 않은 수는 '셀프넘버'입니다.

 

---

 

public class Main {
	public static void main(String[] args) {
		final int MAX_NUM = 10001;
		int[] selfNumberFlag = new int[MAX_NUM];
		
		for(int num=1; num<MAX_NUM; num++) {
			int notSelfNumber = notSelfNumber(num);
			
			if(notSelfNumber < MAX_NUM) {
				selfNumberFlag[notSelfNumber] = 1;
			}
		}
		
		for(int i=1; i<MAX_NUM; i++) {
			if(selfNumberFlag[i] == 0) {
				System.out.println(i);
			}
		}

	}
	
	public static int notSelfNumber(int num) {
		int result = num;
	
		while(num > 0) {
			result += num % 10;
			num /= 10;
		}
		
		return result;
	}
}