백준 2231 python(파이썬)

백준 2231번 파이썬 풀이

---

문제

문제 해석

문제 설명이 약간은 복잡하게 느껴질 수 있지만 꽤나 단순한 문제다.

우선 ‘생성자‘에 대한 이해가 있어야 한다.

예를 들어 123이란 정수는 정수 그대로의 123과 각 자리별 요소인 1,2,3 이 있다.

정수 123 과 각 요소 1,2,3을 더한다면 129라는 정수가 나오고 이때 ‘123’을 ‘129’의 생성자라고 한다.

그리고 ‘129’는 ‘123’의 분해합이다.

생성자의 덧셈식을 통해 분해합이 계산됨으로 생성자는 분해합보다 작을 수 밖에 없다.

한 정수에 대하여 생성자는 여러개가 존재할 수 있다.

정수 10001을 예로들면 10000, 9973 두개의 정수 모두 10001의 생성자가 될 수 있다.

문제 풀이

우선 생성자는 분해합보다 작다는 특징을 생각해서 ‘-1’ 씩 차감하여 차감된 정수의 분해합이 주어진 정수와 일치 여부를 판단하여 생성자 관계를 확인 하면 된다.

여기서 고려해야 될 문제는 정수가 1,000,000까지 주어질 수 있기 때문에 범위를 특정해주지 않는다면 불필요한 연산양이 늘어나서 시간 초과가 나올 확률이 크다.

결국은 분해합=정수+각 자리수(생성자) 이므로 각 자리수가 낼 수 있는 최대의 차이를 구하면 연산 범위를 줄 일 수 있다.

최대값인 1,000,000의 경우 백만자리를 제외하고 총 여섯 자리가 있다.

그리고 각 자리에서 낼 수 있는 최대 차이는 ‘9’ 이므로 ‘분해합 -54’ 이내의 값에서 생성자가 결정 된다.

정답

def selfnum(x): # 생성자 찾기 함수
    num = x
    for j in range(7): #최대 자리수인 7번만큼 반복 
        num = num+x % 10
        x = x//10
    return num


a = int(input())
min = 1000000 # 최소값을 가능한 최대값으로 지정

for i in range(a, a-55, -1): # 최대 차이를 생각하여 -55 까지 반복
    temp = selfnum(i)

    if temp == a and i < min: # 제일 작은 생성자 확인
        ans = i
        min = i

    if i == 1:
        break

if min != 1000000:
    print(min)
else:#최소값이 그대로일 경우 생성자가 없음
    print("0")

문제 링크 : 백준2231