[백준] 2231번 분해합

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

2231번: 분해합

 

풀이

이 문제도 다양한 풀이 방법이 있을 수 있어 가장 직관적인 풀이와 시간을 단축시킬 수 있는 풀이로 구현해봤다.

1. 기본적으로 분해합을 처음 숫자 + 각 자릿수로 구현했기 때문에 해당 방법으로 직관적으로 구현할 수 있다.
숫자의 범위가 100만이기 때문에 문제 없이 풀 수 있다.

N = int(input())

answer = 0

for i in range(1, N):
    temp = i
    for j in str(i):
        temp += int(j)
    if temp == N:
        answer = i
        break

print(answer)

입력받은 숫자의 범위까지 숫자를 문자로 변환하여 접근하면 각 자릿수에 쉽게 접근할 수 있다.

 

위 방법으로 풀게되면 입력이 100만인 경우 1~100만까지 검사하기 때문에 많은 시간이 소요된다.

 

2. 분해합으로 만들 수 있는 숫자의 규칙을 생각해보면 검사할 범위를 줄일 수 있다.
각 자리에서 나올 수 있는 최대 숫자는 9이고 처음 숫자 + 각자릿수를 하기 때문에
입력받은 숫자의 길이가 N일때 N을 만들 수 있는 범위는 N - N*9 ~ N - 1까지이다. 

즉 숫자가 253이라고 가정하면 226(253 - 27) ~ 252까지만 검사를 하면 된다. 

start = N - (9*num_len)
if start < 1:
    start = 1

위 방법으로 시작 범위를 지정하고

for i in range(start, N):
    temp = i
    for j in str(i):
        temp += int(j)
    if temp == N:
        answer = i
        break

print(answer)

첫번째 코드와 동일하게 검사를 진행하면 검사 횟수를 줄일 수 있다.

 

전체 코드

1번

N = int(input())

answer = 0

for i in range(1, N):
    temp = i
    for j in str(i):
        temp += int(j)
    if temp == N:
        answer = i
        break

print(answer)

2번

N = int(input())

num_len = len(str(N))
answer = 0


start = N - (9*num_len)
if start < 1:
    start = 1

for i in range(start, N):
    temp = i
    for j in str(i):
        temp += int(j)
    if temp == N:
        answer = i
        break

print(answer)

 

규칙을 찾는 것으로 코드 수행 시간을 획기적으로 줄일 수 있게 된다.