[백준] 2231번 분해합

링크 : https://www.acmicpc.net/problem/2231

문제

풀이

첫번째 풀이 : 1부터 n까지 부분합을 모두 찾았다

first_n = int(input())
n = 0
flg = 0
while n < first_n:
    n += 1
    n_sum = n
    for i in str(n):
        n_sum += int(i)

    if n_sum == first_n:
        print(n)
        flg = 1
        break

if flg == 0:
    print(0)

두번째 풀이 : 이진탐색 이용

-> 제일 작은 값을 어떻게 찾을지 고민해보자

import sys
input = sys.stdin.readline

first_n = int(input())
answer = []
def binary_search(start,end,target):
    if start>end:
        return 0
    mid = (start+end) // 2
    # n : 분해합
    n = mid
    for i in str(mid):
        n += int(i)

    if target == n:
        return mid
    elif target > n:
        return binary_search(mid, end, target)
    else:
        return binary_search(start, mid, target)

print(binary_search(1,first_n,first_n))