백준 2231번 python 풀이

 

우선 이 문제를 봤을때 비교적 작은 수인 네자리의 숫자는 for문을 n만큼 돌려도 시간이 오래걸리지 않아서

범위 n까지의 숫자중 분해합이 n이 되었을때 가장 작은 수를 출력하도록 했다

 

<초기코드>

n = input()
result = ""
if len(n) < 5:
  i = 0
else:
  i = int(n[:len(n)-3]+"000")

for i in range(i, int(n)):
  m = str(i)
  check = int(m)
  for j in range(len(m)):
    check += int(m[j])
  if check == int(n):
    if result == "":
      result = m
  
if result == "":
  print(0)
else:
  print(result)

하지만 네자리수보다 큰 경우(1000이상) for문을 돌릴때 분명 시간초과가 뜰 것이기 때문에

처음에는 문자열 인덱스를 이용해서 천의 자리보다 큰 값은 고정을 해두고 최대 9999의 반복문이 돌도록 했는데

자꾸 틀리다고 나왔다..

 

질문 게시판에 반례를 테스트해봐도 전부 정답만 출력됐는데

곰곰이 생각하다가 혼자 깨달음을 얻었다

 

90030의 생성자는 89988, 90043의 생성자는 89999였던것...

내가 만든 반복문을 기준으로 따지면 90000부터 반복문을 시작했기에 이런 반례를 잡지 못했던 것이었다

 

반례를 어떻게 찾아야 할지 막막했는데

n의 예시를 생각하는 것보다 m의 예시를 생각하는 편이 훨씬 빠르고 간편했다

 

<최종코드>

n = input()
result = ""
if len(n) < 5:
  i = 0
else:
  i = (int(n[:len(n)-3])-1) * 1000

for i in range(i, int(n)):
  m = str(i)
  check = int(m)
  for j in range(len(m)):
    check += int(m[j])
  if check == int(n):
    if result == "":
      result = m
  
if result == "":
  print(0)
else:
  print(result)

 

제출결과 성공!