[BOJ] 2231 - 분해합 (🥉 브론즈 2티어)

사용 언어: Python3

문제

분해합

풀이

나의 풀이 - 생성자의 각 숫자를 리스트에 담아 sum() 이용

N = int(input()) # N은 분해합

constructor = 0
for i in range(1, N):
    constructor = i # 생성자
    devide_sum = constructor + sum(list(map(int, str(i)))) # 분해합
    
    if devide_sum == N:
        print(constructor)
        break
else:
    print('0')

• 테스트 케이스: 성공
• 제출 결과: 성공

나의 풀이 - while 이용

N = int(input()) # N은 분해합

constructor = 0
for i in range(1, N):
    constructor = i # 생성자
    devide_sum = i # 분해합

    while i > 10:
        devide_sum += i % 10
        i //= 10
    devide_sum += i

    if devide_sum == N:
        print(constructor)
        break
else:
    print('0')

• 테스트 케이스: 성공
• 제출 결과: 성공

다른 풀이

N = int(input()) # N은 분해합

# 생성자 찾기
start = max(0, N - len(str(N)) * 9) # ✅ 탐색 시작 값
for i in range(start, N):
    if i + sum(list(map(int, str(i)))) == N: # 분해합이 N과 같으면
        print(i)
        break
else:
    print('0')

• 테스트 케이스: 성공
• 제출 결과: 성공
• 생성자를 찾을 때, 1부터 모든 경우를 확인하면 너무 오래 걸리므로 각 자리 값이 가장 작은 경우부터 분해합을 구한다.
  • 각 자리의 숫자는 0~9까지 올 수 있다. 따라서 가장 최악의 경우(=모든 자리가 9)를 생각해서 9*(자릿수) 만큼을 뺀 값에서부터 분해합을 구한다.
  • 9*(자릿수)보다 작은 경우들은 0부터 찾아야 한다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기