[알각코] 백준 2231번 - 분해합

백준 2231번

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

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

N = input()

def getSum(strNum):
  nlist = [int(i) for i in list(strNum)]
  nlist.append(int(strNum))
  return sum(nlist)


nDict = {}
n = 1
while n <= 1000000:
  if (getSum(str(n)) not in nDict):
    nDict[getSum(str(n))] = n
  n += 1

print(nDict[int(N)] if int(N) in nDict else 0)

구상

1부터 1000000까지 직접 각 자리 수의 합을 더 더한 값들과 생성자를 같이 튜플에 담아 리스트에 담는다.

다만, 중복된 값들이 생길 경우 그 값은 넣지않는다. 그리고 input 값을 해당 리스트에서 찾아내서 생성자를 프린트 한다.

N = int(input())

def getSum(strNum):
  nlist = [int(i) for i in list(strNum)]
  nlist.append(int(strNum))
  return sum(nlist)


nDict = {}
n = 1
while n <= N:
  if getSum(str(n)) not in nDict:
    nDict[getSum(str(n))] = n
  n += 1

print(nDict[N] if N in nDict else 0)

속도가 너무 느려서 input 값까지 while로 돌도록 수정해보았다

근데 별차이가 없음…

N = int(input())

def getSum(strNum):
  nlist = [int(i) for i in list(strNum)]
  nlist.append(int(strNum))
  return sum(nlist)


nDict = {}
n = 1
while n <= N:
  s = getSum(str(n))
  if s not in nDict:
    nDict[s] = n
  n += 1

print(nDict[N] if N in nDict else 0)

getSum 함수를 두번이나 써서 변수로 할당하여 사용해보았다

속도가 반이나 줄었당

n=int(input())
print([*[i for i in range(n)if n==i+sum(map(int,str(i)))],0][0])

백준 숏코딩을 참조하였다

리스트 앞에 *이 붙으면 unpacking된다고 해서 리스트들이 다 요소로 나열된당

여기에 0도 추가해서 첫번째 값이 무조건 최솟값이 나오는걸 이용해

내 코드에서 하는 체킹이 필요없도록 하였다

백준 2231번

구상

Reference