알고리즘 문제풀이: 셀프 넘버

NameError·2021년 4월 14일

백준4673 백준온라인저지 알고리즘 자료구조

문제 링크

https://www.acmicpc.net/problem/4673

풀이 전 계획과 생각

일단 문제 자체를 이해하기 위해서 구석구석 뜯어보았다.

양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자.
예를 들어, d(75) = 75+7+5 = 87이다.

일단 def d(n):을 만들어봐야겠다.

n을 d(n)의 생성자라고 한다... 생성자가 없는 숫자를 셀프 넘버라고 한다.

그러니까 d(n)의 출력 결과가 되지 않는 수를 셀프 넘버라고 정의할 수 있겠다.

예를 들어서 d(1)=1+1=2니까 2는 셀프 넘버가 아니다.
1=(정수+정수의 자릿수끼리 더한 수)라는 건 성립할 수 없다. 정수끼리 더한다면 1=1+0밖에 없는데 전자와 후자가 각각 1, 0이나 0, 1인 경우는 있을 수 없다. 그러니까 1은 셀프 넘버다.
d(2)=2+2=4니까 4는 셀프 넘버가 아니다.
이런 식으로 주어진 수와 같거나 작은 모든 셀프 넘버가 아닌 수들을 찾은 다음에 셀프 넘버를 찾아보겠다고 생각했다.

'바퀴를 처음부터 발명하려는 현대인'처럼 보이겠지만 일단 별다른 방법이 생각나지 않아서 주어진 수가 몇 자리수인지를 구하고, 그것을 통해서 그 수에서 각 자릿수를 추출하고, 그 결과에 따라서 d(n)을 계산해서 d(n)의 결과가 되는 리스트를 추출하는 과정까지 먼저 함수로 만들어보았다.

def d_count(n):
    s=10
    x=n%10    
    # 1234라는 수의 결과
    # 10 나머지는 4
    # 100 나머지는 34
    # 1000 나머지는 234
    # 10000 나머지는 1234
    while x!=n:
        s*=10
        x=n%s
    return int(s/10)
def ciphers(n):
    m_total = d_count(n)
    m=10
    s=[]
    s.append(n%m)
    while m<=m_total:        
        m*=10 # 100
        # 100으로 나눈 나머지
        m_temp=n%m # 1234를 100으로 나눈 나머지 34
        for i in range(len(s)): #[4]가 있음 
            m_temp-=s[i]*(10**(i))
        #print(m_temp)
        s.append(int(m_temp/(m/10)))
    return s
def d(n):
    ciphers_list = ciphers(n)
    for item in ciphers_list:
        n+=item
    return n
        
def d_list(n):
    smaller_ds = []
    x=1
    while x<=n:
        non_self_number = d(x)
        if non_self_number<=n:
            smaller_ds.append(non_self_number)
        x+=1
    return smaller_ds

여기까지 입력해 두면 d_list(100)의 출력 결과는 이렇다. 이 리스트에 나오지 않는 값들이 셀프 넘버일 것이다.

[2, 4, 6, 8, 10, 12, 14, 16, 18, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 88, 90, 92, 94, 96, 98, 100, 99]

문제 풀이

여기까지 셀프 넘버가 아닌 수를 모두 찾은 다음에 주어진 수보다 작거나 같은 '셀프 넘버가 아닌 수 리스트에 있지 않은 수'를 모두 찾도록 해보았다.

또한 문제의 취지가 '목록을 반환하라'가 아니라 '한 줄에 하나씩 출력하라'니까 출력 과정도 별도로 함수에 넣어두었다.

def self_numbers(n):
    non_self_numbers=d_list(n)
    is_self_numbers=[]
    for i in range(1,n):
        if i not in non_self_numbers:
            is_self_numbers.append(i)
    return is_self_numbers
    
    
def self_numbers_print(n):
    self_numbers_list = self_numbers(n)
    for item in self_numbers_list:
        print(item)