백준 2231번 문제(분해합) 파이썬(Python) 풀이 [로밍맨]

문제 링크

www.acmicpc.net/problem/2231

2231번: 분해합

 

정답 코드는 아래와 같습니다.

def solve():
  n = int(input())
  for i in range(1, n):
    cnt = i
    test = i
    while True:
      cnt += (test % 10)
      test = test // 10
      if test == 0:
        break
    if cnt == n:
      print(i)
      return
  print(0)
 
solve()
 

 

문제에서 주어진 조건을 전체 탐색하여, 조건을 만족하는지 확인하는 식으로 단순하게 풀었습니다.

위에 첨부한 코드와 동영상 모두 이렇게 단순하게 생각해서 풀었는데요.

 

아래와 같은 성질을 이용하면 좀 더 최적화 할 수 있습니다.

"N의 분해합이 6자리 숫자일 때, 분해합의 각 자릿수는 반드시 9보다 작거나 같다.

그렇다면 각 자릿수의 합은 최대 9 * 6 = 54, 즉 54이다.

이는 다시 말해서 N의 분해합이 될 수 있는 가장 작은 수는 N - 54 라는 의미이다."

 

728x90

 

다만, 최적화는 필요에 따라 진행하는 것이 원칙이며,

"정답" 은 이미 달성했기 때문에 상기 내용을 적용하여 최적화하진 않았습니다.

 

풀이는 아래 영상 참고바랍니다.

www.youtube.com/watch?v=f71YBL_2Fpo

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)