브루트 포스> 2231. 분해합

 

<문제링크: www.acmicpc.net/problem/2231>

2231번: 분해합

문제설명: 숫자 N이 주어지고, 각 자리 수와 해당 값의 합으로 이 N을 만들 수 있는 숫자들 중

가장 작은 숫자를 찾는 문제이다. 만약 이처럼 만들 수 없다면, 0을 출력해야 한다.

 

 

[1차 시도]

N = int(input())

minV = 1000000000
check = N

while check>N//2:
    sumup = 0
    num = check
    
    while num>0:
        sumup+=num%10
        num //=10
        
    if check+sumup ==N and check< minV:
        minV = check
        
    check-=1
    
print(minV if minV !=1000000000 else '0')

 

풀이: 정답이 될 수 있는 후보들 중 가장 작은 값을 구하기 위한 minV를 적당히 큰 숫자로 설정해주고, 

N보다 작은 수들 중 후보를 찾아가기 위한 check 변수를 만들어준다.

 

범위를 대략적으로 N의 절반으로 잡아서 while문을 돌려주는데 각 자리수의 합을 저장할 sumup과

각 자리수의 값을 구하기 위한 num을 check로 갱신해준다.

 

그 다음 num이 양수일 때 까지 반복하면서 10으로 나눈 값의 나머지를 sumup에 더해주고

num은 10으로 나눈 값으로 다시 갱신한다.

 

해당 값의 자리수를 다 더해주었으면, 현재의 값인 check와 현재 값의 자리수 합인 sumup을 더한 값이 N과 같고,

현재까지의 최소값보다 작다면, minV를 현재 값 check로 갱신해주면 된다.

 

다시 check는 -1을 해주어 탐색을 계속한다. 

 

최종적으로 minV를 출력해주는데 만약 minV가 처음 초기의 값이라면,

찾고자하는 숫자가 없다는 의미로 0을 출력해주면 된다.

 

 

채첨결과: 정상적으로 잘 통과한다.

 

 

 

 

'쫄보의삽질' 블로그 탄생스토리가 궁금하다면:

Git push 취소 방법 (feat. '쫄보의삽질' 블로그 탄생 배경)