백준 2231번: 분해합
✔ 풀이를 위한 아이디어
- 각 자리수의 합이 최대 얼마나 될 수 있는지 계산해서 탐색의 범위 좁히기
✔ 코드
import sys
N = int(sys.stdin.readline())
#자릿수에 따라 범위를 달리 하는 방법?
#한자리수는 9, 두자리수는 18 이런식으로 할 수 있지만 그럼 또 18 이하에서 나눠야함
rng = 54
if N < 54:
rng = N
for i in range(rng, 0, -1):
M = N - i
sum = 0
for n in str(M): #각 자리수 합을 구할 때는 이렇게 처리하면 된다
sum += int(n)
if sum == i:
print(M)
break
elif i <= 1:
print('0')
break
- 사실 내가 설정한 탐색의 범위가 가장 효율적이라고 할 수는 없다. 최대의 효율로 탐색하려면 자릿수에 따라 범위를 나누되, 18 이하의 수들에 한에서 또 다른 범위를 설정해주면 된다.
- 각 자리수 합을 구할 때 저렇게 하는 것이 효율적이라는 것을 배웠다.
- 처음 시도했을 때는 54 미만의 수들을 고려하지 않아서 런타임 에러가 발생했다.
✔ 관련 개념
- 브루트 포스 알고리즘: https://hcr3066.tistory.com/26
Author And Source
이 문제에 관하여(백준 2231번: 분해합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dlehdtjq00/백준-2231번-분해합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)