118. 분해합

문제
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력
첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

예제 입력 1
216
예제 출력 1
198

1) 어떤 전략(알고리즘)으로 해결?

• 중복순열

2) 코딩 설명

• 중복순열을 사용해서 모든 경우를 탐색하다가 찾게 된다면 프로그램을 종료

<내 풀이>

def find(L):
    global finded
    if finded==1:
        exit
    elif L==lenn :
        cpylenn=lenn
        sum=0
        for i in res :
            if cpylenn == 1:
                sum+=2*i
            else :
                sum+=(10**(cpylenn-1)+1)*i
            cpylenn-=1
        if sum > n:
            return
        if finded==0 and sum == n:
            finded=1
            for i in range(lenn):
                if i==0  and res[i]==0:
                    continue
                print(res[i],end="")
            return  
    else :
        for i in range(0,10):
                res[L]=i
                find(L+1)

if __name__== "__main__" :
    n=int(input())
    lenn=len(str(n))
    res=[0]*lenn #n의 자리수
    finded=0
    find(0)
    if finded == 0:
        print(0)
   

<다른 분의 풀이 or 내 틀린 풀이, 문제점>

def find(L):
    if L==lenn :
        cpylenn=lenn
        sum=0
        for i in res :
            if cpylenn == 1:
                sum+=2*i
            else :
                sum+=(10**(cpylenn-1)+1)*i
            cpylenn-=1
        if sum == n:
            for i in res:
                print(i,end="")
                return  
    else :
        for i in range(1,10):
            if chk[i]==0:
                chk[i]=1
                res[L]=i
                find(L+1)
                chk[i]=0

if __name__== "__main__" :
    n=int(input())
    lenn=len(str(n))
    res=[0]*lenn #n의 자리수
    chk=[0]*(10) #1~9
    find(0)

• 생성자가 없으면 0을 어떻게 출력하게 하지?

시도1)

    if n ==None:
        print(0)

• None 객체를 돌려준다면 0을 출력하도록..
  => 근데 위에 코드에서는 return 값이 존재하지 않아서 언제나 0을 출력 ㅋ 안됨

시도2)

    n=int(input())
    lenn=len(str(n))
    res=[0]*lenn #n의 자리수
    chk=[0]*(10) #1~9
    finded=0
    find(0)
    if finded == 0:
        print(0)

=> finded 라는 변수 추가함
=> sum==n 이며 finded=1로 설정하기
=> find함수 다 돌았는데도 finded=0이다!? => 생성자가 존재하지 않는 것으로 간주

오마이갓!!나 이거 순열로했는데 그러면 안되지..

-> 순열은 한번씩만 사용하는거자나...이문제에서는 적절하지 않지..
예를 들어서 2000이라는 숫자도 고려해야하는데 순열에선 이미 0을 한번쓰면 더 이상 안쓰자나....오마이갓!!!!!!!!!!!!!!!!!!!!!

중복순열로 해야지

chk 아이만 빼면 된당!!!!!!!!

def find(L):
    global finded
    if L==lenn :
        cpylenn=lenn
        sum=0
        for i in res :
            if cpylenn == 1:
                sum+=2*i
            else :
                sum+=(10**(cpylenn-1)+1)*i
            cpylenn-=1
        if sum > n:
            return
        if finded==0 and sum == n:
            finded=1
            for i in range(lenn):
                if i==0  and res[i]==0:
                    continue
                print(res[i],end="")
            return  
    else :
        for i in range(0,10):
                res[L]=i
                find(L+1)

if __name__== "__main__" :
    n=int(input())
    lenn=len(str(n))
    res=[0]*lenn #n의 자리수
    finded=0
    find(0)
    if finded == 0:
        print(0)

흑흑 하지만 시간 초과 걸린다

def find(L):
    global finded
    if finded==1:
        return
    elif L==lenn :
        cpylenn=lenn
        sum=0
        for i in res :
            if cpylenn == 1:
                sum+=2*i
            else :
                sum+=(10**(cpylenn-1)+1)*i
            cpylenn-=1
        if sum > n:
            return
        if finded==0 and sum == n:
            finded=1
            for i in range(lenn):
                if i==0  and res[i]==0:
                    continue
                print(res[i],end="")
            return  
    else :
        for i in range(0,10):
                res[L]=i
                find(L+1)

if __name__== "__main__" :
    n=int(input())
    lenn=len(str(n))
    res=[0]*lenn #n의 자리수
    finded=0
    find(0)
    if finded == 0:
        print(0)
    

---

• 찾으면 프로그램을 종료하도록 exit을 설정해둠 but
  여전히 시간 초과라네..

==> pypy로 하니깐 된다..파야호~

def find(L):
    global finded
    if finded==1:
        exit
    elif L==lenn :
        cpylenn=lenn
        sum=0
        for i in res :
            if cpylenn == 1:
                sum+=2*i
            else :
                sum+=(10**(cpylenn-1)+1)*i
            cpylenn-=1
        if sum > n:
            return
        if finded==0 and sum == n:
            finded=1
            for i in range(lenn):
                if i==0  and res[i]==0:
                    continue
                print(res[i],end="")
            return  
    else :
        for i in range(0,10):
                res[L]=i
                find(L+1)

if __name__== "__main__" :
    n=int(input())
    lenn=len(str(n))
    res=[0]*lenn #n의 자리수
    finded=0
    find(0)
    if finded == 0:
        print(0)
    

<반성 점>

• 문제의 의도를 제대로 파악하지 못한 점
• 언제 순열, 조합 써야하는지, 중복순열, 중복조합을 고려해야하는지 항상 마음에 새기자
• 예외처리 문제도 잘... 처음에 숫자를 1~9로 설정했었다.. 0도 가능한데도..

<배운 점>

• 원하는거 찾으면 프로그램 종료 시켜버리기
  => 설명 출처 블로그

  exit(), die() = 무조건 종료
  프로그램이 강제로 종료된다.

• DFS 순열, 조합코드 복습
  순열

def perm(L):
    if L==m : #m개를 다 뽑은 경우라면
        for i in res :
            print(i, end="")
        print()
    else : 
        for i in range(1,n+1): #1~n 까지에서 뽑는 경우라면
            if chk[i]==0 : 
                chk[i]=1
                res[L]=i
                perm(L+1) #하나뽑았고 가지치기 시작
                chk[i]=0  #back하기 전에 이제 체크해뒀던 건 back에선 풀어조야함
   
if __name__=="__main__":
    #n개에서 m개를 뽑는 경우
    n,m=map(int, input().split())
    chk=[0]*(n+1)
    res=[0]*m
    perm(0)

조합

def comb(L,S) :#가지를 뻗을 때 조합은 순서상관안하고 동일한 것으로 간주
    #따라서 이미 가지뻗었던 경우의 수는 순서 달라도 같다고 간주
    #S를 기준으로 앞에서 이미 뻗었던 애 제외하고 가지 뻗음
    if L==m:#m개 만큼 뽑기 완료했다면
        for j in res:
           print(j,end="")
        print()
    else :
        for i in range(S,n+1):
            res[L]=i
            comb(L+1,i+1) #이때 S가 아닌 i에서부터 가지가 뻗어나가게 된다

if __name__=="__main__" :
    n,m=map(int, input().split())
    res=[0]*m
    comb(0,1)