파이썬 알고리즘 118번 | [백준 2231번] 분해합
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)
Author And Source
이 문제에 관하여(파이썬 알고리즘 118번 | [백준 2231번] 분해합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@myway00/파이썬-알고리즘-118번-백준-번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)