2231: 분해합

2231번: 분해합

2231번: 분해합 문제

---

2231: 분해합

N = int(input())
# N의 생성자 M은 N보다 작거나 같다. (M <= N) 따라서 N의 생성자를 구할 때는 1~N 까지의 수의 생성자를 알아보면 된다.(1 <= M <= N 이므로)

# 매개변수가 생성자인 수를 리턴하는 함수
def d(num): 
    for cycle in str(num):
        num += int(cycle)
    return num

switch = 0
for check in range(1, N):
    if d(check) == N:
        print(check)
        switch =1
        break
if switch == 0:
    print(0)

위 코드는 문제 풀이를 위해 처음 성공한 코드이고, 소스코드를 참고하여 아래 더욱 빠른 코드를 만들었습니다.

---

개선된 점

1. 생성자 M 찾는 시간 단축

2. 출력 간소화 (switch 제거)

참고: https://www.acmicpc.net/source/53309592

 

해설

1. 생성자 M 찾는 시간 단축

 

3자리 수 N의 생성자를 M이라 하면,

M = 100a + 10b + c

N = 100a + 10b + c + ( a + b + c ). (0 <= a, b, c <= 9, a, b, c가 동시에 0을 취하지 않는다.) 

(3자리 수 외에 1, 2자리 수도 포함하고 있는 조건이지만 상관 없다.)

N = M + ( a + b + c )

조건에 따라 1 <= a+b+c <= 27 이며,

M = N - (a + b + c),

N - 27 <= M <= N - 1

따라서 N의 생성자가 되는 M은 최소값은 N-27이다.

일반화: n자리 수인 N의 생성자가 되는 M의 최소값은 N - (9 * n) 이다.

따라서 N의 생성자는 N- (9 * n)부터 N-1 사이에 있다.

하지만 한자리 , 두자리 수 일부(1 ~ 8, 10 ~ 17)는 최솟값(start_check)이 음수부터 시작하므로 함수에 넣는 과정에서 - 연산자가 오류를 만든다. 또한 음수는 애초에 대상이 아니다. 따라서 if 문을 통해 start_check 값을 0으로 치환한다.

2. 출력 간소화 (switch 제거)

print를 if 문을 통해 두 개로 나눠 출력한 코드를 변수 값을 바꿔 한 개의 print문으로 출력하도록 변경하였다.

기존

조건에 따라 switch, check 둘 중 하나를 출력. ( 변수 두 개를 사용해 이해하기 복잡)

변경

→ switch, check의 값을 조건에 따라 M에 담은  후, M을 출력

N = int(input())

# M이 될 수 있는 최솟값
start_check = N - len(str(N)) * 9
if start_check < 0:
    start_check = 0
    
# 매개변수가 생성자인 수를 리턴하는 함수
def d(num): 
    return num + sum(list(map(int,list(str(num)))))

M = 0
for check in range(start_check, N):
    if d(check) == N:
        M = check
        break
print(M)​

 

연관 문제로 4673번: 셀프 넘버가 있으니 같이 풀어보시면 좋을 것 같습니다.

 

4673번: 셀프 넘버

 

오류, 개선점, 궁금한 점이 있으시다면 댓글로 남겨주세요. 감사합니다:)